最小スパニングツリー

グラフの最小スパニング ツリーは、合計の重みが最小のスパニング ツリーです。

グラフには多数のスパニング ツリーが含まれる場合があります。エッジに重みが付けられているとします。最小スパニング ツリーには最小の合計重みがあります。たとえば、以下の図 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 – T から T に頂点 (v とします) を継続的に追加します。 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 に追加します。これは、Edge(2, 6, 5) が <🎜 の頂点に属するすべてのエッジの中で最も重みが小さいためです。 >T、図 d に示すように 頂点 4 を
T
6. に追加します。これは、Edge(4, 6, 7) が <🎜 の頂点に属するすべてのエッジの中で最も重みが小さいためです。 >T (図 e に示すように) Edge(3, 2, 8) の重みが <🎜 の頂点に属するすべてのエッジの中で最小であるため、3 を
T
7. に追加します。 >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)

程序为上图第 27 行创建一个加权图。然后调用 getMinimumSpanningTree()（第 28 行）返回一个 MST，它表示图形。在 MST 对象上调用 printTree()（第 30 行）会显示树中的边缘。请注意，MST 是 Tree 的子类。 printTree() 方法定义在 Tree 类中。

最小生成树的图示如下图所示。顶点按以下顺序添加到树中：西雅图、旧金山、洛杉矶、丹佛、堪萨斯城、达拉斯、休斯顿、芝加哥、纽约、波士顿、亚特兰大和迈阿密。

以上が最小スパニングツリーの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。