加權(quán)圖是一種為每條邊關(guān)聯(lián)一個權(quán)值或是成本的圖模型。這種圖能夠自然地表示許多應(yīng)用。在一幅航空圖中，邊表示航線，權(quán)值則可以表示距離或是費用。在這些情形中，最令人感興趣的自然是將成本最小化。這里用加權(quán)無向圖模型來解決最小生成樹：給定一幅加權(quán)無向圖，找到它的一棵最小生成樹。

圖的生成樹是它的一棵含有其所有頂點的無環(huán)連通子圖。一幅加權(quán)圖的最小生成樹（MST）是它的一棵權(quán)值（樹中所有邊的權(quán)值之和）最小的生成樹。

計算最小生成樹的兩種經(jīng)典算法：Prim 算法和 Kruskal 算法。

1.原理

樹的兩個重要性質(zhì)：

1.用一條邊連接樹中的任意兩個頂點都會產(chǎn)生一個新的環(huán)；

2.從樹中刪除一條邊將會得到兩棵獨立的樹。

這兩條性質(zhì)是證明最小生成樹的另一條基本性質(zhì)的基礎(chǔ)，而由這條基本性質(zhì)就能夠得到最小生成樹的算法。

1.切分定理

我們稱之為切分定理的這條性質(zhì)將會把加權(quán)圖中的所有所有頂點分為兩個集合，檢查橫跨兩個集合的所有邊并識別哪條邊應(yīng)屬于圖的最小生成樹。

通常，我們指定一個頂點集并隱式地認為它地補集為另一個頂點集來指定一個切分。這樣，一條橫切邊就是連接該集合地一個頂點和不在該集合地另一個頂點地一條邊。

切分定理：在一幅加權(quán)圖中，給定任意得切分，它的橫切邊中權(quán)重最小者必然屬于圖的最小生成樹。

注意，權(quán)重最小的橫切邊并不一定是所有橫切邊中唯一屬于圖的最小生成樹的邊。實際上，許多切分都會產(chǎn)生若干條屬于最小生成樹的橫切邊：

2.貪心算法

切分定理是解決最小生成樹問題的所有算法的基礎(chǔ)。更確切的說，這些算法都是一種貪心算法的特殊情況：使用切分定理找到最小生成樹的一條邊，不斷重復(fù)直到找到最小生成樹的所有便。這些算法之間的不同之處在于保存切分和判定權(quán)重最小的橫切邊的方式，但它們都是一下性質(zhì)特殊情況：

最小生成樹的貪心算法：下面這種算法會將含有 V 個頂點的任意加權(quán)連通圖中屬于最小生成樹的邊標記為黑色：初始狀態(tài)下所有邊均為灰色，找到一種切分，它產(chǎn)生的橫切邊均不為黑色。將它權(quán)重最小的橫切邊標記為黑色。反復(fù)，直到標記了 V - 1 條黑色邊為止。

2.加權(quán)無向圖的數(shù)據(jù)類型

namespace MinimumSpanningTrees
{
    public class Edge:IComparable<Edge>
    {
        private int v;//頂點之一
        private int w;//另一個頂點
        private double weight;//邊的權(quán)重

        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);
        }
    }
}

加權(quán)無向圖的實現(xiàn)使用了 Edge 對象。

namespace MinimumSpanningTrees
{
    public class EdgeWeightedGraph
    {
        private int v;//頂點總數(shù)
        private int e;//邊的總數(shù)
        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];
        }
    }
}

為了整潔，用一對 int 值和一個 double 值表示每個 Edge 對象。實際的數(shù)據(jù)結(jié)構(gòu)是一個鏈表，其中每個元素都是一個指向含有這些值的對象的指針。需要注意的是，雖然每個Edge對象都有兩個引用，但圖中的每條邊所對應(yīng)的 Edge 對象只有一個。

• 用權(quán)重來比較邊

Edge 類實現(xiàn)了 IComparable 接口的CompareTo 方法。一幅加權(quán)無向圖中的邊的自然次序就是按權(quán)重排序。

• 平行邊

和無環(huán)圖的實現(xiàn)一樣，這里也允許存在平行邊。我們也可以用更復(fù)雜的方法來消除平行邊，比如保留平行邊中權(quán)重最小者。

• 自環(huán)

允許存在自環(huán)，這對最小生成樹算法沒有影響，因為最小生成樹肯定不會含有自環(huán)。

有個 Edge 對象之后用例的代碼就可以變得更加干凈整潔。這也有小的代價：每個鄰接表的結(jié)點都是一個都是一個指向 Edge 對象的引用，它們含有一些冗余的信息， v 的鄰接鏈表中的每個結(jié)點都會用一個變量保存 v 。使用對象也會帶來一些開銷。雖然每條邊的 Edge 對象都只有一個，但鄰接表中還是會含有兩個指向同一 Edge 對象的引用。

另一種廣泛使用的方案是與 Graph 一樣，用兩個結(jié)點對象表示一條邊，每個結(jié)點對象都會保存頂點的信息和邊的權(quán)重。這種方法也是有代價的 -- 需要兩個結(jié)點，每條邊的權(quán)重都會被保存兩次。

3.最小生成樹 API

按照慣例，在 API 中會定義一個接受加權(quán)無向圖為參數(shù)的構(gòu)造函數(shù)并且支持能夠為用例返回圖的最小生成樹和其權(quán)重的方法。那么應(yīng)該如何表示最小生成樹？由于圖的最小生成樹是圖的一幅子圖并且同時也是一棵樹，因此可以有一下選擇：

• 1.一組邊的列表；
• 2.一幅加權(quán)無向圖；
• 3.一個以頂點為索引且含有父結(jié)點鏈接的數(shù)組。

在為了各種應(yīng)用選擇這些表示方法時，我們希望盡可能給予最小生成樹的實現(xiàn)以最大的靈活性，采用如下 API ：

4.Prim 算法

Prim 算法，它的每一步都會為一棵生長中的樹添加一條邊。一開始這棵樹只有一個頂點，然后會向它添加 V-1 條邊，每次總是將下一條連接樹中的頂點與不在樹中的頂點且權(quán)重最小的邊加入樹中。

Prim 算法能夠得到任意加權(quán)連通圖的最小生成樹。這棵不斷生長的樹定義了一個切分且不存在樹中的橫切邊。該算法會選擇權(quán)重最小的橫切邊并根據(jù)貪心算法不斷將他們標記。

數(shù)據(jù)結(jié)構(gòu)

實現(xiàn) Prim 算法需要一些簡單常見的數(shù)據(jù)結(jié)構(gòu)。具體來說，我們會用一下方法表示樹中的頂點，邊和橫切邊：

1.頂點：使用一個由頂點索引的布爾數(shù)組 marked[ ] ，如果頂點 v 在樹中，那么 marked[v] 的值為 true。

2.邊：選擇以下兩種數(shù)據(jù)結(jié)構(gòu)之一：一條隊列 mst 來保存最小生成樹中的邊，或者一個由頂點索引的Edge對象的數(shù)組 edgeTo[ ] ，其中edgeTo[ v ] 為將 v 連接到樹中的 Edge 對象；

3.橫切邊：使用一條優(yōu)先隊列 MinPQ<Edge> 來根據(jù)權(quán)重比較所有邊。

有了這些數(shù)據(jù)結(jié)構(gòu)就可以回答 “哪條邊的權(quán)重最小” 這個基本問題了。

維護橫切邊的集合

每當我們向樹中添加了一條邊后，也向樹中添加一個頂點。要維護一個包含所有橫切邊的集合，就要將連接這個頂點（新加入樹）和其他所有不在樹中的頂點的邊加入優(yōu)先隊列。但還有一點：連接新加入樹中的頂點和其他已經(jīng)在樹中的頂點的所有邊都要失效（這樣的邊已經(jīng)不是橫切邊了，因為它的兩個頂點都在樹中）。Prim 算法的即時實現(xiàn)可以將這樣的邊從優(yōu)先隊列中刪掉，先來看一種延時實現(xiàn)，將這些邊先留在優(yōu)先隊列中，等到要刪除它們的時候再檢查邊的有效性。

算法構(gòu)造最小生成樹的過程：

1.將頂點 0 添加到最小生成樹，將它的鄰接鏈表中的所有邊添加到優(yōu)先隊列中。

2.取權(quán)重最小的邊 0-7，將頂點 7 和 邊 0-7 添加到最小生成樹中，將頂點 7 的鄰接鏈表中的所有邊添加到優(yōu)先隊列中。

3.將頂點 1 和邊 1-7 添加到最小生成樹中，將頂點的鄰接鏈表中的所有邊添加到優(yōu)先隊列中。

4.將頂點 2 和邊 0-2 添加到最小生成樹，將邊 2-3 和 6-2 添加到優(yōu)先隊列。邊 2-7 和 1-2 失效（因為邊的兩個頂點都在樹中，最后刪除）。

5.將頂點 3 和邊 2-3 添加到最小生成樹，將邊 3-6 添加到優(yōu)先隊列。邊 1-3 失效。

6.將頂點 5 和邊 5-7 添加到最小生成樹，將邊 4-5 添加到優(yōu)先隊列。邊 1-5 失效。

7.從優(yōu)先隊列刪除失效的邊 1-3，1-5 和 2-7 。

8.將頂點 4 和邊 4-5 添加到最小生成樹中，將邊 6-4 添加到優(yōu)先隊列。邊 4-7 和 0-4 失效。

9.從優(yōu)先隊列刪除失效的邊 1-2，4-7 和 0-4 。

10.將頂點 6 和邊 6-2 添加到最小生成樹中，和頂點 6 相關(guān)聯(lián)的其他邊均失效。

在添加了 V 個頂點以及 V-1 條邊之后，最小生成樹就完成了。優(yōu)先隊列中剩下的邊都是無效的，可以不用去檢查。

實現(xiàn)

我們使用一個私有方法 Visit（）來為樹添加一個頂點，將它標記為“已訪問”并將與它關(guān)聯(lián)的所有未失效的邊加入優(yōu)先隊列，以保證隊列含有所有連接樹頂點和非樹頂點的邊（也可能含有一些已失效的邊）。代碼的內(nèi)循環(huán)是算法的具體實現(xiàn)：從優(yōu)先隊列中取出一條邊并將它添加到樹中（如果沒有失效），再把這條邊的另一個頂點也添加到樹中，然后用新頂點作為參數(shù)調(diào)用 Visit 方法來更新橫切邊的集合。 Weight 方法可以遍歷樹的所有邊并得到權(quán)重之和。

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());
        }
    }
}

性能

Prim 算法的延時實現(xiàn)計算一幅含有 V 個頂點和 E 條邊的連通加權(quán)無向圖的最小生成樹所需的空間和 E 成正比，所需的時間與 ElogE成正比（最壞情況）。算法的瓶頸在于優(yōu)先隊列的刪除和添加方法中比較邊的權(quán)重的次數(shù)。優(yōu)先隊列最多可能含有 E 條邊，這就是空間需求的上限。在最壞情況下，一次插入成本為 ～lgE ，刪除最小元素的成本為 ~2lgE 。因為最多只能插入 E 條邊，刪除 E 次最小元素，時間上限顯而易見。

5. Prim 算法的即時實現(xiàn)

要改進LazyPrimMST ，可以嘗試從優(yōu)先隊列中刪除失效的邊，這樣優(yōu)先隊列就只有樹頂點和非樹頂點之間的橫切邊，但還可以刪除更多的邊。關(guān)鍵在于，我們感興趣的只是連接樹頂點和非樹頂點中權(quán)重最小的邊。當我們將頂點 v 添加到樹中，對于每個非樹頂點 w 產(chǎn)生的變化只可能使得 w 到最小生成樹的距離更近。簡而言之，我們不需要在優(yōu)先隊列中保存所有從 w 到樹頂點的邊 —— 而只需保存其中權(quán)重最小的那條。在將 v 添加到樹中后檢查是否需要更新這條權(quán)重最小的邊（因為 v-w 的權(quán)重可能更?。?。我們只需遍歷 v 的鄰接鏈表就可以完成這個任務(wù)。換句話說，我們只會在優(yōu)先隊列中保存每個非樹頂點 w 的一條邊：將它與樹中頂點連起來的權(quán)重最小的那條邊。將 w 和樹的頂點連接起來的其他權(quán)重較大的邊遲早都會失效，所以沒必要在優(yōu)先隊列中保存他們。

算法類 PrimMST 將 LazyPrimMST 類中 marked[ ] 和 mst[ ] 替換為兩個頂點索引的數(shù)組 edgeTo[ ] 和 distTo[ ] ：

• 1.如果頂點 v 不在樹中但至少含有一條邊和樹相連，那么 edgeTo[v] 是將 v 和樹連接的最短邊，distTo[v] 為這條邊的權(quán)重。
• 2.所有這類頂點 v 都保存在一條索引優(yōu)先隊列中，索引 v 關(guān)聯(lián)的值是 edgeTo[v] 的邊的權(quán)重。

這些性質(zhì)的關(guān)鍵在于優(yōu)先隊列中的最小鍵即是權(quán)重最小的橫切邊的權(quán)重，而和它相關(guān)聯(lián)的頂點 v 就是下一個將被添加到樹中的頂點。marked[ ] 數(shù)組已經(jīng)沒有必要了，因為判斷條件 ！marked[w] 等價于 distTo[w] 是無窮的（且 edgeTo[w] 為 null）。要維護這些數(shù)據(jù)結(jié)構(gòu)，PrimMST 會從優(yōu)先隊列中取出一條邊并檢查它的鄰接鏈表中的每條邊 v-w 。如果 w 已經(jīng)被標記過，那這條邊就已經(jīng)失效了；如果 w 不在優(yōu)先隊列中或者 v-w 的權(quán)重小于目前已知的最小值 edgeTo[w]，代碼會更新數(shù)組，將 v-w 作為將 w 和樹連接的最佳選擇。

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 和權(quán)重 0 初始化 pq
            while (pq.Count > 0)
            {
                Visit(G,pq.DelMin());//將最近的頂點添加到樹中
            }
        }

        private void Visit(EdgeWeightedGraph G, int v)
        {
            //將頂點 v 添加到樹中，更新數(shù)據(jù)
            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]);
                }
            }
        }
    }
}

Prim 算法的即時實現(xiàn)計算一幅含有 V 個頂點和 E 條邊的連通加權(quán)無向圖的最小生成樹所需的空間和 V 成正比，所需的時間與 ElogV成正比（最壞情況）。

6.Kruskal 算法

第二種生成最小生成樹的主要思想是按照邊的權(quán)重順序（從小到大）處理它們，將邊加入最小生成樹中，加入的邊不會與已經(jīng)加入的邊構(gòu)成環(huán)，直到樹中含有 V-1 條邊為止。這些邊逐漸由一片森林合共成一棵樹。

為什么 Kruskal 算法能夠計算任意加權(quán)連通圖的最小生成樹？

如果下一條將被加入最小生成樹中的邊不會和已有的邊構(gòu)成環(huán)，那么它就跨越了由所有和樹頂點相鄰的頂點組合的合集以及它們的補集所構(gòu)成的一個切分。因為加入的邊不會形成環(huán)，它是目前已知的唯一一條橫切邊且是按照權(quán)重順序選擇的邊，所以它必然是權(quán)重最小的橫切邊。因此，該算法能夠連續(xù)選擇權(quán)重最小的橫切邊，和貪心算法一致。

Prim 算法是一條邊一條邊地來構(gòu)造最小生成樹，每一步都為一棵樹添加一條邊。 Kruskal 算法構(gòu)造最小生成樹地時候也是一條邊一條邊地構(gòu)造，但不同的是它尋找的邊會連接一片森林中的兩棵樹。我們從一片由 V 棵單頂點的樹構(gòu)成的森林開始并不斷將兩棵樹合并（用可以找到的最短邊）直到只剩下一棵樹，它就是最小生成樹。

實現(xiàn)

我們將會使用一條優(yōu)先隊列來將邊按照權(quán)重排序，用一個 union-find 數(shù)據(jù)結(jié)構(gòu)來識別會形成環(huán)的邊，以及一條隊列來保存最小生成樹的所有邊。

    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 得到權(quán)重最小的邊和它的頂點
                int v = e.Either(), w = e.Other(v);

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

Kruskal 算法的計算一幅含有 V 個頂點和 E 條邊的連通加權(quán)無向圖的最小生成樹所需的空間和 E 成正比，所需的時間和 ElogE 成正比（最壞情況）。

算法的實現(xiàn)在構(gòu)造函數(shù)中使用所有邊初始化優(yōu)先隊列，成本最多為 E 次比較（請見 union-find）。優(yōu)先隊列構(gòu)造完成后，其余的部分和 Prim 算法完全相同。優(yōu)先隊列中最多可能含有 E 條邊，即所需空間的上限。每次操作的成本最多為 2lgE 次比較，這就是時間上限的由來。 Kruskal 算法最多還會進行 E 次 Connected（） 和 V 次 Union（）操作，但這些成本相比 ElogE 的總時間的增長數(shù)量級可以忽略不計。

與 Prim 算法一樣，這個估計是比較保守的，因為算法在找到 V-1 條邊之后就會終止。實際成本應(yīng)該與 E+E0 logE 成正比，其中 E0 是權(quán)重小于最小生成樹中權(quán)重最大的邊的所有邊的總數(shù)。盡管擁有這個優(yōu)勢，Kruskal 算法一般還是比 Prim 算法要慢，因為在處理每條邊時，兩種方法都要完成優(yōu)先隊列操作之外，它還需要進行一次 Connect（） 操作。

到此這篇關(guān)于C#圖表算法之最小生成樹的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支持腳本之家。