7. Spanning trees

Spanning trees in DS

1. 1 Spanning Trees

2. 2 Graph - Spanning Tree A tree that contains every vertex of a connected graph is called spanning tree. It is an undirected tree consisting of only those edges that are necessary to connect all the vertices of the original graph G. CHARACTERISTICS  It is a subgraph of a graph G that  contain all the vertex  of graph G. For any pair of vertices, there exists only one path between them. It is a connected graph with  no cycles . A graph may have  many  spanning tree.

3. 3 EXAMPLE

4. 4 Graph - Minimum Spanning Tree Let G=(V,E,W) be any weighted graph. Then a spanning tree whose cost is minimum is called  minimum spanning tree . The cost of the spanning tree is defined as the sum of the costs of the edges in that tree.

5. 5 Kruskal's algorithm It is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). Kruskal's algorithm is an example of a greedy algorithm.

6. 6 Create a forest F (a set of trees), where each vertex in the graph is a separate tree Create a set S containing all the edges in the graph Repeat Step 4 and 5, while S is nonempty and F is not yet spanning Remove an edge with minimum weight from S IF that edge connects two different trees, then add it to the forest, combining two trees into a single tree ELSE discard that edge. Exit At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph.

7. 7 Example of Kruskal’s Algorithm This is our original graph. The numbers near the arcs indicate their weight. None of the arcs are highlighted.

8. 8 AD and CE are the shortest arcs, with length 5, and AD has been arbitrarily chosen, so it is highlighted. CE is now the shortest arc that does not form a cycle, with length 5, so it is highlighted as the second arc.

9. 9 The next arc, DF with length 6, is highlighted using much the same method. The next-shortest arcs are AB and BE, both with length 7. AB is chosen arbitrarily, and is highlighted. The arc BD has been highlighted in red, because there already exists a path (in green) between B andD, so it would form a cycle (ABD) if it were chosen.

10. 10 The process continues to highlight the next-smallest arc, BE with length 7. Many more arcs are highlighted in red at this stage: BC because it would form the loop BCE, DE because it would form the loop DEBA, and FE because it would form FEBAD. Finally, the process finishes with the arc EG of length 9, and the minimum spanning tree is found.

11. 11 Prim's algorithm It is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. Same as in Kruskal’s Algorithm, it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. It is also sometimes called the DJP algorithm, the Jarnik algorithm, or the Prim–Jarnik algorithm.

12. 12 Prim's algorithm (contd..) The only spanning tree of the empty graph (with an empty vertex set) is again the empty graph. The following description assumes that this special case is handled separately. The algorithm continuously increases the size of a tree, one edge at a time, starting with a tree consisting of a single vertex, until it spans all vertices.

13. 13 Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative). Algorithm: Initialize: V new = {x}, where x is an arbitrary node (starting point) from V, E new = { } Repeat Step 3 and 4, until V new = V Choose an edge (u, v) with minimal weight such that u is in V new and v is not (if there are multiple edges with the same weight, any of them may be picked) Add v to V new , and (u, v) to E new Exit Output: V new and E new describe a minimal spanning tree

14. 14 Example of Prim’s Algorithm This is our original weighted graph. The numbers near the edges indicate their weight.

15. 15 Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD. The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the arc DF.

16. 16 The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted. In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away from B, and G is 11 away from F. E is nearest, so we highlight the vertex E and the arc BE.

17. 17 Here, the only vertices available are C and G. C is 5 away from E, and G is 9 away from E. C is chosen, so it is highlighted along with the arc EC. Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight it and the arc EG.

18. 18 Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.

19. 19 U Edge(u,v) V - U { } {A,B,C,D,E,F,G} {D} (D,A) = 5   V (D,B) = 9 (D,E) = 15 (D,F) = 6 {A,B,C,E,F,G} {A,D} (D,B) = 9 (D,E) = 15 (D,F) =6   V (A,B) = 7 {B,C,E,F,G} {A,D,F} (D,B) = 9 (D,E) = 15 (A,B) = 7   V (F,E) = 8 (F,G) = 11 {B,C,E,G} {A,B,D,F} (B,C) = 8 (B,E) = 7   V (D,B) = 9 cycle (D,E) = 15 (F,E) = 8 (F,G) = 11 {C,E,G} {A,B,D,E,F} (B,C) = 8 (D,B) = 9 cycle (D,E) = 15 cycle (E,C) = 5   V (E,G) = 9 (F,E) = 8 cycle (F,G) = 11 {C,G} {A,B,C,D,E,F} (B,C) = 8 cycle (D,B) = 9 cycle (D,E) = 15 cycle (E,G) = 9   V (F,E) = 8 cycle (F,G) = 11 {G} {A,B,C,D,E,F,G} (B,C) = 8 cycle (D,B) = 9 cycle (D,E) = 15 cycle (F,E) = 8 cycle (F,G) = 11 cycle { }