C#图表算法之最小生成树

namespace MinimumSpanningTrees
{
    public class Edge:IComparable<Edge>
    {
        private int v;//顶点之一
        private int w;//另一个顶点
        private double weight;//边的权重

        public Edge(int v, int w, double weight)
        {
            this.v = v;
            this.w = w;
            this.weight = weight;
        }

        public double Weight()
        {
            return weight;
        }

        public int Either()
        {
            return v;
        }

        public int Other(int vertex)
        {
            if (vertex == v)
                return w;
            else if (vertex == w)
                return v;
            else
                throw new ArgumentException();
        }



        public int CompareTo([AllowNull] Edge other)
        {
            if (this.Weight() < other.Weight())
                return -1;
            else if (this.Weight() > other.Weight())
                return 1;
            else
                return 0;
        }

        public override string ToString()
        {
            return string.Format("%d-%d %.2f",v,w,weight);
        }
    }
}

namespace MinimumSpanningTrees
{
    public class EdgeWeightedGraph
    {
        private int v;//顶点总数
        private int e;//边的总数
        private List<Edge>[] adj;//邻接表

        public EdgeWeightedGraph(int V)
        {
            this.v = V;
            e = 0;
            adj = new List<Edge>[V];
            for (int _v = 0; _v < V; _v++)
            {
                adj[_v] = new List<Edge>();
            }
        }

        public int V()
        {
            return v;
        }

        public int E()
        {
            return e;
        }

        public void AddEdge(Edge edge)
        {
            int v = edge.Either();
            int w = edge.Other(v);

            adj[v].Add(edge);
            adj[w].Add(edge);

            e++;
        }

        public IEnumerable<Edge> Adj(int _v)
        {
            return adj[_v];
        }
    }
}

namespace MinimumSpanningTrees
{
    public class LazyPrimMST
    {
        private bool[] marked;//最小生成树的顶点
        private Queue<Edge> mst;//最小生成树的边
        private MinPQ<Edge> pq;//横切边（包括失效的边）

        public LazyPrimMST(EdgeWeightedGraph G)
        {
            pq = new MinPQ<Edge>();
            marked = new bool[G.V()];
            mst = new Queue<Edge>();

            Visit(G,0);
            while (!pq.Count > 0)
            {
                Edge e = pq.Dequeue();

                int v = e.Either();
                int w = e.Other(v);
                if (marked[v] && marked[w])
                    continue;
                pq.Enqueue(e);

                if (!marked[v])
                    Visit(G,v);
                if (!marked[w])
                    Visit(G,w);
            }
        }

        private void Visit(EdgeWeightedGraph G, int v)
        {
            marked[v] = true;
            foreach (Edge e in G.Adj(v))
            {
                if (!marked[e.Other(v)])
                    pq.Enqueue(e);
            }
        }

        public IEnumerable<Edge> Edges()
        {
            return mst;
        }

        public double Weight()
        {
            return mst.Sum(o=>o.Weight());
        }
    }
}

namespace MinimumSpanningTrees
{
    public class PrimMST
    {
        private Edge[] edgeTo;//距离树最近的边
        private double[] distTo;//distTo[w]=edgeTo[w].weight()
        private bool[] marked;//如果 v 在树中则为 true
        public IndexMinPQ<double> pq;//有效的横切边

        public PrimMST(EdgeWeightedGraph G)
        {
            edgeTo = new Edge[G.V()];
            distTo = new double[G.V()];
            marked = new bool[G.V()];

            for (int v = 0; v < G.V(); v++)
            {
                distTo[v] = Double.MaxValue;
            }

            pq = new IndexMinPQ<double>(G.V());

            distTo[0] = 0.0;
            pq.Insert(0,0.0); //用顶点 0 和权重 0 初始化 pq
            while (pq.Count > 0)
            {
                Visit(G,pq.DelMin());//将最近的顶点添加到树中
            }
        }

        private void Visit(EdgeWeightedGraph G, int v)
        {
            //将顶点 v 添加到树中，更新数据
            marked[v] = true;
            foreach (Edge e in G.Adj(v))
            {
                int w = e.Other(v);

                if (marked[w])
                    continue;

                if (e.Weight() < distTo[w])
                {
                    edgeTo[w] = e;
                    distTo[w] = e.Weight();

                    if (pq.Contains(w))
                        pq.Change(w, distTo[w]);
                    else
                        pq.Insert(w,distTo[w]);
                }
            }
        }
    }
}

    public class KruskalMST
    {
        private Queue<Edge> mst;
        public KruskalMST(EdgeWeightedGraph G)
        {
            mst = new Queue<Edge>();//最小生成树的边
            MinPQ<Edge> pq = new MinPQ<Edge>(G.Edges);//所有边
            UF uf = new UF(G.V());

            while (!pq.IsEmpty() && mst.Count < G.V() - 1)
            {
                Edge e = pq.DelMin();//从 pq 得到权重最小的边和它的顶点
                int v = e.Either(), w = e.Other(v);

                if (uf.Connected(v, w))//忽略失效的边
                    continue;
                uf.Union(v,w);//合并分量
                mst.Enqueue(e);//将边添加到最小生成树中
            }
        }
    }