linux - 如何使用 graph-viz 在复杂图形上实现 'finding min-spanning tree algorithm'？

Question

我需要使用 graph-viz 在大图中找到最小生成树。节点数和边信息将在另一个文本文件中的 2 列“源”和“目标”中给出。请帮忙。

Answer 1

Graphviz 主要是一种布局图形的工具。包含的算法与此任务相关。图的输入是图规范。

您需要的是一个计算 MST 的工具。有几个。维基百科文章是引用的良好开端:

http://en.wikipedia.org/wiki/Prim's_algorithm

在python中有

http://pygraphviz.github.io/

在 perl 中，我发现

https://gist.github.com/hirotnk/780342

这里的答案是:

Graphviz Dot Algorithm

也是一个很好的引用。

根据 MST 工具的输出，您可以生成由 graphviz 渲染的文件。