1CMSC 132: Object-Oriented Programming IIMinimal Spanning Tree AlgorithmsDepartment of Computer ScienceUniversity of Maryland, College Park2OverviewSpanning treesMinimum spanning tree (MST)Prim’s algorithmKruskal’s algorithmGraph implementationAdjacency list / matrix / set3Spanning TreeSet of edges connecting all nodes in graphneed N-1 edges for N nodesno cycles, can be thought of as a treeCan build tree during traversal4Spanning Tree ConstructionRecursive algorithmKnown = { start }explore ( start );void explore (Node X) {for each successor Y of Xif (Y is not in Known)Parent[Y] = XAdd Y to Knownexplore(Y) }5Spanning Tree ConstructionIterative algorithmKnown = { start }Discovered = { start }while ( Discovered ≠≠≠≠ ∅∅∅∅ ) {take node X out of Discoveredfor each successor Y of Xif (Y is not in Known)Parent[Y] = XAdd Y to DiscoveredAdd Y to Known }6Breadth & Depth First Spanning TreesBreadth-first Depth-first7Depth-First Spanning Tree Example8Breadth-First Spanning Tree Example9Spanning Tree ConstructionMany spanning trees possibleDifferent breadth-first traversalsNodes same distance visited in different orderDifferent depth-first traversalsNeighbors of node visited in different orderDifferent traversals yield different spanning trees10Minimum Spanning Tree (MST)Spanning tree with minimum total edge weight11Minimum Spanning Tree (MST)Possible to have multiple MSTsDifferent spanning trees with same weightExample applicationsMinimize length of telephone lines for neighborhoodMinimize distance of airplane routes serving cities12Algorithms for Finding MSTThree well known algorithms 1.Borůvka’s algorithm [1926]For constructing efficient electricity networkRediscovered by Sollin in 1960s2.Prim’s algorithm [1957]First discovered by Vojtěch Jarník in 1930Similar to Djikstra’s algorithm3.Kruskal’s algorithm [1956]By Prof. Clyde Kruskal’s uncle13Algorithms for Finding MST1.Borůvka’s algorithmAdd vertices to MST in parallel2.Prim’s algorithmAdd vertices to MST One at a timeClosest vertex first3.Kruskal’s algorithmAdd edges to MSTOne at a timeLightest edge first14Shortest Path – Dijkstra’s AlgorithmS = ∅∅∅∅P[ ] = none for all nodesC[start] = 0, C[ ] = ∞∞∞∞ for all other nodeswhile ( not all nodes in S )find node K not in S with smallest C[K]add K to S for each node J not in S adjacent to K if ( C[K] + cost of (K,J) < C[J] ) C[J] = C[K] + cost of (K,J) P[J] = KOptimal solution computed with greedy algorithm15MST – Prim’s AlgorithmS = ∅∅∅∅P[ ] = none for all nodesC[start] = 0, C[ ] = ∞∞∞∞ for all other nodeswhile ( not all nodes in S )find node K not in S with smallest C[K]add K to S for each node J not in S adjacent to K if ( /* C[K] + */ cost of (K,J) < C[J] ) C[J] = /* C[K] + */ cost of (K,J) P[J] = KKeeps track of vertex w/ minimal distance to current treeOptimal solution computed with greedy algorithm16MST – Kruskal’s Algorithmsort edges by weight (from least to most)tree = ∅∅∅∅for each edge (X,Y) in orderif it does not create a cycleadd (X,Y) to treestop when tree has N–1 edgesKeeps track oflightest edge remainingwhether adding edge to MST creates cycleOptimal solution computed with greedy algorithm17MST – Kruskal’s Algorithm Example18MST – Kruskal’s AlgorithmWhen does adding (X,Y) to tree create cycle?Two approaches to finding cycles1.Traversal2.Connected subgraph19MST – Kruskal’s AlgorithmTraversal approachTraverse tree starting at XIf we can reach Y, adding (X,Y) would create cycleExampleQuestionAdd (X,Y) to MST?AnswerNo, since can alreadyreach Y from X by traversing MSTxyzw?20MST – Kruskal’s AlgorithmConnected subgraph approachMaintain set of nodes for each connected subgraphInitialize one connected subgraph for each nodeIf X, Y in same set, adding (X,Y) would create cycleOtherwise1.Add edge (X,Y) to spanning tree 2.Merge sets containing X, YTo test set membershipUse Union-Find algorithm21MST – Connected Subgraph Example22MST – Connected Subgraph Example23Union-Find AlgorithmUnion-FindAlgorithm & data structure Very efficient for testing membership in disjoint setsProblem descriptionStart with n nodes, each in different subgraphSupport two operationsFind – are nodes x & y in same subgraph?Union – merge subgraphs containing x & y24Union-Find AlgorithmBasic approachEach node has a parent pointerFind – follow parent pointer(s) to root of treeUnion – point root of 1sttree to root of 2ndtreeExampleUnion( a, b ) ; union( c , d); union( b, d)a b c d abc d abcdab cd25Union-Find AlgorithmPath compressionSpeeds up future Find( ) operations1.Follow parent pointer(s) to root of tree2.Update all nodes along path to point to rootExampleFind(d)ab cdab c dSo how fast is Union-Find?26Ackermann’s FunctionFunctionint A(x,y) {if (x == 0) return y+1;if (y == 0) return A(x – 1, 1);return A(x – 1, A(x, y – 1));}A( ) grows fastA(2,2) = 7A(3,3) = 61A(4,2) = 265536– 3A(4,3) = 2265536– 3 A(4,4) = 22265536– 327Inverse Ackermann’s FunctionDefinitionαααα(n) is the inverse Ackermann’s functionαααα(n) = the smallest k such that A(k,k) ≥nFun factαααα(number of atoms in universe) = 4Union-findA sequence of n operations requires O(n αααα(n) ) timePractically speaking, indistinguishable from O(n)28Graph SummaryGraph data structureVery useful in practiceDifferent representationsMany graph algorithmsTraversalShortest pathMinimum spanning
View Full Document
Unlocking...