最小生成樹

圖的最小生成樹是總權重最小的生成樹。

一個圖可能有許多生成樹。假設邊緣被加權。最小生成樹的總權重最小。例如，下圖 b、c、d 中的樹是圖 a 中圖的生成樹。圖c和d中的樹是最小生成樹。

尋找最小生成樹的問題有很多應用。考慮一家在許多城市設有分公司的公司。該公司希望租用電話線將所有分公司連接在一起。電話公司對連接不同的城市收取不同的費用。有多種方法可以將所有分支連接在一起。最便宜的方法是找出總費率最小的生成樹。

最小生成樹演算法

如何找到最小生成樹？有幾種眾所周知的演算法可以做到這一點。本節介紹Prim演算法。 Prim 的演算法從包含任一頂點的生成樹 T 開始。此演算法透過重複添加具有與樹中已有頂點相關的最低成本邊的頂點來擴展樹。 Prim的演算法是一種貪心演算法，其程式碼如下所示。

Input: A connected undirected weighted G = (V, E) with non-negative weights
 Output: MST (a minimum spanning tree)
 1 MST minimumSpanningTree() {
 2 Let T be a set for the vertices in the spanning tree;
 3 Initially, add the starting vertex to T;
 4
 5 while (size of T < n) {
 6 Find u in T and v in V – T with the smallest weight
 7 on the edge (u, v), as shown in Figure 29.6;
 8 Add v to T and set parent[v] = u;
 9 }
10 }

演算法首先將起始頂點加入T中。然後，它不斷地將一個頂點（例如 v）從 V – T 添加到 T 中。 v 是與 T 中的頂點相鄰且邊權重最小的頂點。例如，T 和V – T 中的頂點有5 條邊連接，如下圖所示，並且(u, v ) 是權重最小的一個。

考慮下圖中的圖表。此演算法會以以下順序將頂點加入 T：

1. 將頂點 0 加入 T。
2. 將頂點5 加到T，因為Edge(5, 0, 5) 在與<🎜 中的頂點關聯的所有邊中具有最小的權重>T，如圖a所示。由 0 到 5 的箭頭線表示 0 是 5 的父級。
將頂點
3. 1 加到T，因為Edge(1, 0, 6) 在與<🎜 中的頂點關聯的所有邊中具有最小的權重>T，如圖b. 將頂點
6
4. 加到T，因為Edge(6, 1, 7) 在與<🎜 中的頂點關聯的所有邊中具有最小的權重>T，如圖c. 將頂點2
加到
5. T，因為邊（2,6,5）在與<🎜中的頂點相關的所有邊中具有最小的權重>T，如圖d. 將頂點4加到
T
6. ，因為邊（4,6,7）在與<🎜中的頂點關聯的所有邊中具有最小的權重>T，如圖e. 將頂點3加到T
，因為
7. 邊（3,2,8）在與<🎜中的頂點相關的所有邊中具有最小的權重>T，如圖f. 最小生成樹不是唯一的。例如，下圖中的 (c) 和 (d) 都是圖 a 中的圖的最小生成樹。但是，如果權重不同，則該圖具有唯一的最小生成樹。

假設圖是連通且無向的。如果圖沒有連通或有向，則演算法將不起作用。您可以修改演算法來尋找任何無向圖的生成林。生成森林是一個圖，其中每個連接的組件都是一棵樹。

Refining Prim’s MST Algorithm

To make it easy to identify the next vertex to add into the tree, we use cost[v] to store the cost of adding a vertex v to the spanning tree T. Initially cost[s] is 0 for a starting vertex and assign infinity to cost[v] for all other vertices. The algorithm repeatedly finds a vertex u in V – T with the smallest cost[u] and moves u to T. The refined version of the alogrithm is given in code below.

Input: A connected undirected weighted G = (V, E) with non-negative weights
Output: a minimum spanning tree with the starting vertex s as the root
 1 MST getMinimumSpanngingTree(s) {
 2 Let T be a set that contains the vertices in the spanning tree;
 3 Initially T is empty;
 4 Set cost[s] = 0; and cost[v] = infinity for all other vertices in V;
 5
 6 while (size of T < n) {
 7 Find u not in T with the smallest cost[u];
 8 Add u to T;
 9 for (each v not in T and (u, v) in E)
10 if (cost[v] > w(u, v)) { // Adjust cost[v]
11 cost[v] = w(u, v); parent[v] = u;
12 }
13 }
14 }

Implementation of the MST Algorithm

The getMinimumSpanningTree(int v) method is defined in the WeightedGraph class. It returns an instance of the MST class, as shown in Figure below.

The MST class is defined as an inner class in the WeightedGraph class, which extends the Tree class, as shown in Figure below.

The Tree class was shown in Figure below. The MST class was implemented in lines 141–153 in WeightedGraph.java.

The refined version of the Prim’s algoruthm greatly simplifies the implementation. The getMinimumSpanningTree method was implemented using the refined version of the Prim’s algorithm in lines 99–138 in Listing 29.2. The getMinimumSpanningTree(int startingVertex) method sets cost[startingVertex] to 0 (line 105) and cost[v] to infinity for all other vertices (lines 102–104). The parent of startingVertex is set to -1 (line 108). T is a list that stores the vertices added into the spanning tree (line 111). We use a list for T rather than a set in order to record the order of the vertices added to T.

Initially, T is empty. To expand T, the method performs the following operations:

1. Find the vertex u with the smallest cost[u] (lines 118–123 and add it into T (line 125).
2. After adding u in T, update cost[v] and parent[v] for each v adjacent to u in V-T if cost[v] > w(u, v) (lines 129–134).

After a new vertex is added to T, totalWeight is updated (line 126). Once all vertices are added to T, an instance of MST is created (line 137). Note that the method will not work if the graph is not connected. However, you can modify it to obtain a partial MST.

The MST class extends the Tree class (line 141). To create an instance of MST, pass root, parent, T, and totalWeight (lines 144-145). The data fields root, parent, and searchOrder are defined in the Tree class, which is an inner class defined in AbstractGraph.

Note that testing whether a vertex i is in T by invoking T.contains(i) takes O(n) time, since T is a list. Therefore, the overall time complexity for this implemention is O(n3).

The code below gives a test program that displays minimum spanning trees for the graph in Figure below and the graph in Figure below a, respectively.

package demo;

public class TestMinimumSpanningTree {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
                {1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
                {2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
                {3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
                {4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
                {5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
                {6, 5, 983}, {6, 7, 214},
                {7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
                {8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
                {9, 8, 661}, {9, 11, 1187},
                {10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
                {11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
        };

        WeightedGraph<String> graph1 = new WeightedGraph<>(vertices, edges);
        WeightedGraph<String>.MST tree1 = graph1.getMinimumSpanningTree();
        System.out.println("Total weight is " + tree1.getTotalWeight());
        tree1.printTree();

        edges = new int[][]{
            {0, 1, 2}, {0, 3, 8},
            {1, 0, 2}, {1, 2, 7}, {1, 3, 3},
            {2, 1, 7}, {2, 3, 4}, {2, 4, 5},
            {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
            {4, 2, 5}, {4, 3, 6}
        };

        WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
        WeightedGraph<Integer>.MST tree2 = graph2.getMinimumSpanningTree(1);
        System.out.println("\nTotal weight is " + tree2.getTotalWeight());
        tree2.printTree();
    }

}

Total weight is 6513.0
Root is: Seattle
Edges: (Seattle, San Francisco) (San Francisco, Los Angeles)
(Los Angeles, Denver) (Denver, Kansas City) (Kansas City, Chicago)
(New York, Boston) (Chicago, New York) (Dallas, Atlanta)
(Atlanta, Miami) (Kansas City, Dallas) (Dallas, Houston)

Total weight is 14.0
Root is: 1
Edges: (1, 0) (3, 2) (1, 3) (2, 4)

The program creates a weighted graph for Figure above in line 27. It then invokes getMinimumSpanningTree() (line 28) to return an MST that represents a minimum spanning tree for the graph. Invoking printTree() (line 30) on the MST object displays the edges in the tree. Note that MST is a subclass of Tree. The printTree() method is defined in the Tree class.

The graphical illustration of the minimum spanning tree is shown in Figure below. The vertices are added to the tree in this order: Seattle, San Francisco, Los Angeles, Denver, Kansas City, Dallas, Houston, Chicago, New York, Boston, Atlanta, and Miami.

以上是最小生成樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！