最小生成树快速图

Question

我想使用快速图找到以下图形的最小生成树。我已经阅读了提供的手册，但我不太明白如何操作。 这是我的代码：

 static void Main(string[] args)
        {

        var g = new UndirectedGraph<int, TaggedUndirectedEdge<int,int>>();

        var e1 = new TaggedUndirectedEdge<int, int>(1, 2, 57);
        var e2 = new TaggedUndirectedEdge<int, int>(1, 4, 65);
        var e3 = new TaggedUndirectedEdge<int, int>(2, 3, 500);
        var e4 = new TaggedUndirectedEdge<int, int>(2, 4, 1);
        var e5 = new TaggedUndirectedEdge<int, int>(3, 4, 78);
        var e6 = new TaggedUndirectedEdge<int, int>(3, 5, 200);

        g.AddVerticesAndEdge(e1);
        g.AddVerticesAndEdge(e2);
        g.AddVerticesAndEdge(e3);
        g.AddVerticesAndEdge(e4);
        g.AddVerticesAndEdge(e5);
        g.AddVerticesAndEdge(e6);

        foreach (var v in g.Edges)
            Console.WriteLine(v);
}

感谢您的帮助。

- cgadjoro

---

你读过 http://quickgraph.codeplex.com/wikipage?title=Minimum%20Spanning%20Tree 吗？ - daryal

是的，我看到了，但当我读到这一行时有点迷茫：“Func<TEdge, double> edgeWeights = ...;” - cgadjoro

Answer 1

@daryal 比我快一步了-我的版本是：

var mst = g.MinimumSpanningTreePrim(e => e.Tag).ToList();  

"使用源代码，卢克"——我查看了MinimumSpanningTreeTest.cs，测试了Prim12273

(此外，您可以查看关于Lambda / Delegates的问题，以更好地理解基本函数指针)

- mhoff

Answer 2

假设TaggedUndirectedEdge的最后一个参数Tag表示边的权重，那么以下代码可能有效。

Func<TEdge, double> edgeWeights = (q) => {
g.Edges.SingleOrDefault(m => q == m).Tag;
}

IEnumerable<TEdge> mst = g.MinimumSpanningTreePrim(g, edgeWeights);

- daryal