我正在实现(实际上考虑它)一个控件，允许用户从一系列节点创建一个网络图表。目的是根据软件另一部分提出的一系列问题创建一个“流程图”；对于每个问题，选择的答案决定了接下来应该问哪个问题。它有点 FSMish，但比“如果你对问题 Y 回答 X，请回答以下……”形式的线性问题要聪明得多。该图是一个网络，不能保证是一棵树，因为定义该图的用户可能想问几个后续问题，然后返回到“正常”的提问线，因此两个不同的节点可能会“合并”到同一个子节点。然而，网络保证不是圆形的并且有一个起点，因此通过图形的路径数量有限，并且所有路径的长度都是有限的。
问题来了。我想要一个“排列”按钮(或简单地自动排列)来重新排列节点，以便连接必须相互交叉的网络节点的线数最小化。大多数流程图工具都有执行此操作的功能，但我的 Google-fu 未能找到这种类型的通用算法。我已将其确定为“交叉数”问题，但似乎没有找到具有 V 节点和 E 路径的图的最小交叉数的通用解决方案，并且任何此类解决方案都是 NP-hard(如果一个特定的子问题可以在单个操作中解决，然后整个问题可以在多项式时间内解决)。最重要的是，我发现没有任何引用文献详细说明了可以用最小(更不用说“最小”)交叉数布置图形的算法。
有什么提示吗？
编辑: 我给 Sharkos 打勾，因为他提供了出色的引用资料。然而，假设图形有一个明确的起点，是单向的和非循环的，一个可行的算法(可能不是最优的)实际上非常简单。在伪代码中:
"
Give all nodes an initial XScore, YScore and LinkScore of 0
Determine the start node (either designated, or the one not linked to by any other)
Set start node's XScore and YScore to 1
Set running YScore = 1
Start recursion
for each path from node
if node on other end has XScore <= current
set other node's XScore to current + 1
if node on other end has YScore <= running YScore
set other node's YScore to running YScore
increment other node's LinkScore
Recurse with node on other end
Increment running YScore
Order nodes by XScore, then YScore.
--If the graph happens to be planar, we're done.
--To minimize crossover:
for each XScore
for each node with that XScore
if the next node with the same XScore has a higher LinkScore
swap the two nodes, exchanging YScores
最佳答案
这是一个 Master's thesis在这个主题上，它给出了一些算法并进行了讨论，并提供了很多不同人的方法的引用，从精确算法到近似算法。
然而，对于“平面化方法”的一个相当简单、具体的伪代码版本，显然(不是专家，尽管我研究过图论并且它听起来很有用)一个常见的近似值，参见 this chapter 中的第 2.5 节。来自 Handbook of Graph Drawing and Visualization ，可在线免费获得。
希望这就是您想要的那种东西？
关于.net - 最小化网络图中的交叉线，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11890168/