최소 스패닝 트리

그래프의 최소 스패닝 트리는 총 가중치가 최소인 스패닝 트리입니다.

그래프에는 여러 개의 스패닝 트리가 있을 수 있습니다. 가장자리에 가중치가 부여되어 있다고 가정합니다. 최소 스패닝 트리는 최소 총 가중치를 갖습니다. 예를 들어 아래 그림 b, c, d의 트리는 그림 a의 그래프에 대한 스패닝 트리입니다. 그림 c와 d의 트리는 최소 신장 트리입니다.

최소 스패닝 트리를 찾는 문제는 다양한 용도로 사용됩니다. 여러 도시에 지점이 있는 회사를 생각해 보세요. 회사는 모든 지점을 함께 연결하기 위해 전화선을 임대하려고 합니다. 전화 회사는 여러 쌍의 도시를 연결하기 위해 서로 다른 금액을 청구합니다. 모든 지점을 함께 연결하는 방법에는 여러 가지가 있습니다. 가장 저렴한 방법은 총 비율이 최소인 스패닝 트리를 찾는 것입니다.

최소 스패닝 트리 알고리즘

최소 스패닝 트리는 어떻게 찾나요? 이를 수행하기 위한 몇 가지 잘 알려진 알고리즘이 있습니다. 이번 섹션에서는 Prim의 알고리즘을 소개합니다. Prim의 알고리즘은 임의의 정점을 포함하는 스패닝 트리 T로 시작합니다. 알고리즘은 이미 트리에 있는 정점에 최저 비용 가장자리가 있는 정점을 반복적으로 추가하여 트리를 확장합니다. 프림의 알고리즘은 그리디 알고리즘이며, 아래 코드에 설명되어 있습니다.

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의 정점(예: v)을 T에 계속 추가합니다. v는 가장자리에서 가중치가 가장 작은 T의 정점에 인접한 정점입니다. 예를 들어 아래 그림과 같이 T와 V – T의 정점을 연결하는 5개의 간선이 있고, (u, v )의 무게가 가장 작은 것입니다.

아래 그림의 그래프를 살펴보세요. 알고리즘은 다음 순서로 T에 정점을 추가합니다.

1. T에 정점 0을 추가합니다.
2. 정점 5을 T에 추가합니다. Edge(5, 0, 5)는 <🎜에서 정점에 입사하는 모든 가장자리 중에서 가중치가 가장 작기 때문입니다. >T, 그림 a와 같습니다. 0에서 5까지의 화살표는 0이 5의 상위임을 나타냅니다.
정점
3. 1을 T에 추가합니다. Edge(1, 0, 6)은 <🎜에서 정점에 입사하는 모든 가장자리 중에서 가중치가 가장 작기 때문입니다. >T, 그림 b와 같습니다.
T
4. 에 정점 6을 추가합니다. Edge(6, 1, 7)은 <🎜에서 정점에 입사하는 모든 가장자리 중 가중치가 가장 작기 때문입니다. >T, 그림 c와 같습니다. T
에 정점
5. 2를 추가합니다. Edge(2, 6, 5)는 <🎜에서 정점에 입사하는 모든 가장자리 중 가중치가 가장 작기 때문입니다. >T, 그림 d와 같습니다. T에 정점
4
6. 를 추가합니다. Edge(4, 6, 7)은 <🎜에서 정점에 입사하는 모든 가장자리 중에서 가중치가 가장 작기 때문입니다. >T, 그림 e와 같습니다. 정점 3을 T
에 추가합니다.
7. Edge(3, 2, 8)은 <🎜에서 정점에 입사하는 모든 가장자리 중에서 가중치가 가장 작기 때문입니다. >T, 그림 f와 같습니다. 최소 스패닝 트리는 고유하지 않습니다. 예를 들어 아래 그림의 (c)와 (d)는 모두 그림 a의 그래프에 대한 최소 신장 트리입니다. 그러나 가중치가 서로 다른 경우 그래프에는 고유한 최소 스패닝 트리가 있습니다.

그래프가 연결되어 있고 방향이 없다고 가정합니다. 그래프가 연결되지 않거나 방향이 지정되지 않으면 알고리즘이 작동하지 않습니다. 방향이 지정되지 않은 그래프에 대한 확장 포리스트를 찾기 위해 알고리즘을 수정할 수 있습니다. 스패닝 포레스트(Spanning Forest)는 연결된 각 구성 요소가 트리인 그래프입니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!