Arbres couvrant minimum

Un arbre couvrant minimum d'un graphique est un arbre couvrant avec les poids totaux minimaux.

Un graphique peut avoir de nombreux arbres couvrants. Supposons que les bords soient pondérés. Un arbre couvrant minimum a les poids totaux minimum. Par exemple, les arbres des figures ci-dessous b, c, d sont des arbres couvrant pour le graphique de la figure a. Les arbres des figures c et d sont des arbres couvrant minimum.

Le problème de trouver un arbre couvrant minimum a de nombreuses applications. Prenons l’exemple d’une entreprise ayant des succursales dans de nombreuses villes. L'entreprise souhaite louer des lignes téléphoniques pour relier toutes les succursales entre elles. La compagnie de téléphone facture différents montants pour connecter différentes paires de villes. Il existe de nombreuses façons de relier toutes les branches entre elles. Le moyen le moins cher est de trouver un arbre couvrant avec les tarifs totaux minimum.

Algorithmes d'arbre couvrant minimum

Comment trouver un arbre couvrant minimum ? Il existe plusieurs algorithmes bien connus pour ce faire. Cette section présente l'algorithme de Prim. L'algorithme de Prim commence par un arbre couvrant T qui contient un sommet arbitraire. L'algorithme étend l'arbre en ajoutant à plusieurs reprises un sommet avec l'arête au moindre coût incident à un sommet déjà dans l'arbre. L'algorithme de Prim est un algorithme glouton, et il est décrit dans le code ci-dessous.

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 }

L'algorithme commence par ajouter le sommet de départ dans T. Il ajoute ensuite continuellement un sommet (disons v) de V – T dans T. v est le sommet adjacent au sommet dans T avec le plus petit poids sur l'arête. Par exemple, il y a cinq arêtes reliant les sommets dans T et V – T comme le montre la figure ci-dessous, et (u, v ) est celui qui a le plus petit poids.

Considérez le graphique de la figure ci-dessous. L'algorithme ajoute les sommets à T dans cet ordre :

1. Ajouter le sommet 0 à T.
2. Ajoutez le sommet 5 à T, puisque Edge(5, 0, 5) a le plus petit poids parmi toutes les arêtes incidentes à un sommet dans T, comme le montre la figure a. La ligne fléchée de 0 à 5 indique que 0 est le parent de 5.
3. Ajoutez le sommet 1 à T, puisque Edge(1, 0, 6) a le plus petit poids parmi toutes les arêtes incidentes à un sommet dans T, comme le montre la figure b.
4. Ajoutez le sommet 6 à T, puisque Edge(6, 1, 7) a le plus petit poids parmi toutes les arêtes incidentes à un sommet dans T, comme le montre la figure c.
5. Ajoutez le sommet 2 à T, puisque Edge(2, 6, 5) a le plus petit poids parmi toutes les arêtes incidentes à un sommet dans T, comme le montre la figure d.
6. Ajoutez le sommet 4 à T, puisque Edge(4, 6, 7) a le plus petit poids parmi toutes les arêtes incidentes à un sommet dans T, comme le montre la figure e.
7. Ajoutez le sommet 3 à T, puisque Edge(3, 2, 8) a le plus petit poids parmi toutes les arêtes incidentes à un sommet dans T, comme le montre la figure f.

Un arbre couvrant minimum n'est pas unique. Par exemple, (c) et (d) dans la figure ci-dessous sont des arbres couvrants minimaux pour le graphique de la figure a. Cependant, si les poids sont distincts, le graphique a un arbre couvrant minimum unique.

Supposons que le graphique soit connecté et non orienté. Si un graphique n’est pas connecté ou orienté, l’algorithme ne fonctionnera pas. Vous pouvez modifier l'algorithme pour trouver une forêt couvrante pour tout graphique non orienté. Une forêt couvrante est un graphe dans lequel chaque composant connecté est un arbre.

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 클래스

에 정의되어 있습니다.

아래 그림은 최소 스패닝 트리의 그래픽 그림입니다. 정점은 시애틀, 샌프란시스코, 로스앤젤레스, 덴버, 캔자스시티, 댈러스, 휴스턴, 시카고, 뉴욕, 보스턴, 애틀랜타, 마이애미 순서로 트리에 추가됩니다.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!