图中的边缘交叉减少

Question

我想问你是否有任何算法如何最小化图中的边缘交叉,例如,如果我有一个图的转换矩阵.

我找到了尝试将节点放在另一个节点周围的方法,但我想知道其他一些想法.谢谢.

Answer 1

有一系列为图形绘制应用程序开发的成熟算法/库，您可以在此处了解一些背景知识。

要绘制无向图，一种流行的选择是基于力的布局算法，其中图边被视为弹簧（吸引力），而顶点被视为带电粒子（施加排斥力）。该算法的工作原理是根据这些力更新顶点位置，直到达到稳定状态。您可以在此处阅读有关基于力的方法的更多信息。由于这些算法寻找平衡解决方案，因此它们通常会产生伪最优布局，而没有太多边缘缠结。

您可能有兴趣使用众多可用的图形绘制库之一。Graphviz包总体来说相当不错，并且支持针对不同图形绘制应用程序的多种不同算法。