Spanning Tree Based Network Topology DesignKruskal's algorithmKruskal's algorithmSlide 4Kruskal’s AlgorithmSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Prim’s AlgorithmWalk-ThroughSlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Spanning Tree Based Network Topology Design•A spanning tree is the smallest connected network topology that includes all nodes.–Unconstrained Miniumum Weight Spanning Tree (MWST)Kruskal's algorithm•Idea: greedy algorithm. Always add the next cheapest link that does not form a circle (loop) with the already selected links.–Worst-case complexity: O(n2) for a graph with n nodes.Kruskal's algorithm•Idea: grow a spanning tree by adding in each step the cheapest link between the existing tree and the rest of the graph (this automatically guarantees loop avoidance).–Worst-case complexity: O(n2) for a graph with n nodes.•What is the difference between the two algorithms? –In Prim's algorithm we grow one tree until it becomes a spanning tree. –In Kruskal's algorithm we grow a forest (i.e., possibly several trees) until they finally merge into a single spanning tree.© 2010 Goodrich, TamassiaKruskal’s AlgorithmMaintain a partition of the vertices into clustersInitially, single-vertex clustersKeep an MST for each clusterMerge “closest” clusters and their MSTsA priority queue stores the edges outside clustersKey: weightElement: edgeAt the end of the algorithmOne cluster and one MSTMinimum Spanning Trees 5Algorithm KruskalMST(G)for each vertex v in G doCreate a cluster consisting of vlet Q be a priority queue.Insert all edges into QT {T is the union of the MSTs of the clusters}while T has fewer than n - 1 edges doe Q.removeMin().getValue()[u, v] G.endVertices(e)A getCluster(u) B getCluster(v) if A B thenAdd edge e to TmergeClusters(A, B)return TKruskal’s Algorithm•Two steps:–Sort edges by increasing edge weight–Select the first |V| – 1 edges that do not generate a cycleWalk-ThroughConsider an undirected, weight graph51AHBFEDCG3246343484310Sort the edges by increasing edge weightedge dv(D,E) 1 (D,G) 2 (E,G) 3 (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Accepting edge (E,G) would create a cycleSelect first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG3246343484310edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10Select first |V|–1 edges which do not generate a cycleedge dv(D,E) 1(D,G) 2(E,G) 3(C,D) 3(G,H) 3 (C,F) 3(B,C) 451AHBFEDCG2333edge dv(B,E) 4(B,F) 4(B,H) 4(A,H) 5(D,F) 6(A,B) 8(A,F) 10DoneTotal Cost = dv = 214}not consideredDavid Luebke 21 01/14/2019Prim’s AlgorithmMST-Prim(G, w, r) Q = V[G]; for each u Q key[u] = ; key[r] = 0; p[r] = NULL; while (Q not empty) u = ExtractMin(Q); for each v Adj[u] if (v Q and w(u,v) < key[v]) p[v] = u; key[v] = w(u,v);Walk-ThroughInitialize arrayK dvpvA F B F C F D F E F F F G F H F 425AHBFEDCG7210183437893102425AHBFEDCG721018343789310Start with any node, say DK dvpvABC D T 0EFGH2425AHBFEDCG721018343789310Update distances of adjacent, unselected nodesK dvpvABC 3 DD T 0E 25 DF 18 DG 2 DH2425AHBFEDCG721018343789310Select node with minimum distanceK dvpvABC 3 DD T 0E 25 DF 18 DG T 2 DH2425AHBFEDCG721018343789310Update distances of adjacent, unselected nodesK dvpvABC 3 DD T 0E 7 GF 18 DG T 2 DH 3 G2425AHBFEDCG721018343789310Select node with minimum distanceK dvpvABC T 3 DD T 0E 7 GF 18 DG T 2 DH 3 G2425AHBFEDCG721018343789310Update distances of adjacent, unselected nodesK dvpvAB 4 CC T 3 DD T 0E 7 GF 3 CG T 2 DH 3 G2425AHBFEDCG721018343789310Select node with minimum distanceK dvpvAB 4 CC T 3 DD T 0E 7 GF T 3 CG T 2 DH 3 G2425AHBFEDCG721018343789310Update distances of adjacent, unselected nodesK dvpvA 10 FB 4 CC T 3 DD T 0E 2 FF T 3 CG T 2 DH 3 G2425AHBFEDCG721018343789310Select node with minimum distanceK dvpvA
View Full Document
Unlocking...