Graphs & Graph Algorithms 2OverviewSpanning TreeSpanning Tree ConstructionBreadth & Depth First Spanning TreesDepth-First Spanning Tree ExampleBreadth-First Spanning Tree ExampleMinimum Spanning Tree (MST)MST – Kruskal’s AlgorithmMST – Kruskal’s Algorithm ExampleSlide 11MST – Connected Subgraph ExampleSlide 13Single Source Shortest PathShortest Path – Djikstra’s AlgorithmSlide 16Shortest Path – Intuition for Djikstra’sSlide 18Djikstra’s Shortest Path ExampleSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Graph ImplementationAdjacency MatrixSlide 32Slide 33Adjacency ListSlide 35Graph Space RequirementsGraph Time RequirementsGraphs & Graph Algorithms 2 Fawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewSpanning treesMinimum spanning treeKruskal’s algorithmShortest pathDjikstra’s algorithmGraph implementationAdjacency list / matrixSpanning TreeTree connecting all nodes in graphN-1 edges for N nodesCan build tree during traversalSpanning Tree Constructionfor all nodes Xset X.tag = False set X.parent = Null{ Discovered } = { 1st node }while ( { Discovered } )take node X out of { Discovered }if (X.tag = False)set X.tag = True for each successor Y of Xif (Y.tag = False)set Y.parent = X // add (X,Y) to treeadd Y to { Discovered }Breadth & Depth First Spanning TreesBreadth-first Depth-firstDepth-First Spanning Tree ExampleBreadth-First Spanning Tree ExampleMinimum Spanning Tree (MST)Spanning tree with minimum total edge weight Multiple MSTs possible (with same weight)MST – 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 edgesOptimal solution computed with greedy algorithmMST – Kruskal’s Algorithm ExampleMST – Kruskal’s AlgorithmWhen does adding (X,Y) to tree create cycle?1. Traversal approach1. Traverse tree starting at X2. Cycle if reach Y 2. Connected subgraph approach1. Maintain set of nodes for each connected subgraph2. Initialize one connected subgraph for each node3. When edge (X,Y) is added to treeMerge sets containing X, Y4. Cycle if X,Y in same setMST – Connected Subgraph ExampleMST – Connected Subgraph ExampleSingle Source Shortest PathCommon graph problemFind path from X to Y with lowest edge weightFind path from X to any Y with lowest edge weightUseful for many applicationsShortest route in mapLowest cost tripMost efficient internet routeCan solve both problems with same algorithmShortest Path – Djikstra’s AlgorithmMaintainNodes with known shortest path { S }Cost of shortest path to node C[…]For paths through nodes in { S }AlgorithmRepeat until all nodes in { S }Find node K not in { S } with smallest C[ K ]Add K to { S }Update C[M] for all neighbors M of K not in { S }By checking whether C[M] can be reduced by first going to K, then adding weight for edge (K,M)Shortest Path – Djikstra’s Algorithm{ S } = C[X] = 0C[Y] = 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 M not in { S } adjacent to K C[M] = min ( C[M] , C[K] + cost of (K,M) )Optimal solution computed with greedy algorithmShortest Path – Intuition for Djikstra’sAt each step in the algorithmShortest paths are known for nodes in { S }Store in C[K] length of shortest path to node K (for all paths through nodes in { S } )Add to { S } next closest node { S }Shortest Path – Intuition for Djikstra’sUpdate distance to J after adding node KPrevious shortest paths already in C[ K ]Possibly shorter path by going through node KCompare C[ J ] to C[ K ] + weight of (K,J)Djikstra’s Shortest Path ExampleInitial state{ S } = C[1] = 0C[2] = C[3] = C[4] = C[5] = Djikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to { S }{ S } = 1C[1] = 0C[2] = C[3] = C[4] = C[5] = Djikstra’s Shortest Path ExampleUpdate C[K] for all neighbors of 1 not in { S }{ S } = 1C[1] = 0C[2] = 5 C[3] = 8 C[4] = C[5] = C[2] = min ( , C[1] + (1,2) ) = min ( , 0 + 5) = 5C[3] = min ( , C[1] + (1,3) ) = min ( , 0 + 8) = 8Djikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to { S }{ S } = 1, 2C[1] = 0C[2] = 5 C[3] = 8 C[4] = C[5] = Djikstra’s Shortest Path ExampleUpdate C[K] for all neighbors of 2 not in { S }{ S } = 1, 2C[1] = 0C[2] = 5 C[3] = 6 C[4] = 15 C[5] = C[3] = min (8 , C[2] + (2,3) ) = min (8 , 5 + 1) = 6C[4] = min ( , C[2] + (2,4) ) = min ( , 5 + 10) = 15Djikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to { S }{ S } = 1, 2, 3C[1] = 0C[2] = 5 C[3] = 6 C[4] = 15 C[5] = Djikstra’s Shortest Path ExampleUpdate C[K] for all neighbors of 3 not in { S }{ S } = 1, 2, 3C[1] = 0C[2] = 5 C[3] = 6 C[4] = 9 C[5] = C[4] = min (15 , C[3] + (3,4) ) = min (15 , 6 + 3) = 9Djikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to { S }{ S } = 1, 2, 3, 4C[1] = 0C[2] = 5 C[3] = 6 C[4] = 9 C[5] = Djikstra’s Shortest Path ExampleUpdate C[K] for all neighbors of 4 not in { S }{ S } = 1, 2, 3, 4C[1] = 0C[2] = 5 C[3] = 6 C[4] = 9 C[5] = 18 C[4] = min ( , C[4] + (4,5) ) = min ( , 9 + 9) = 18Djikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to { S }{ S } = 1, 2, 3, 4, 5C[1] = 0C[2] = 5 C[3] = 6 C[4] = 9 C[5] = 18Djikstra’s Shortest Path ExampleNo more nodes in { S }{ S } = 1, 2, 3, 4, 5C[1] = 0C[2] = 5 C[3] = 6 C[4] = 9 C[5] = 18Graph ImplementationRepresentationsExplicit edges (a,b)Maintain set of edges for every nodeAdjacency matrix2D array of neighborsAdjacency listLinked list of neighborsImportant for very large graphsAffects efficiency / storageAdjacency MatrixRepresentation2D arrayPosition j, k edge between nodes nj, nkUnweighted graph Matrix elements booleanWeighted graph Matrix elements weightAdjacency MatrixExampleAdjacency MatrixPropertiesSingle array for entire graphOnly upper / lower triangle matrix needed for undirected graphSince nj, nk implies nk, njAdjacency ListRepresentationLinked list for each nodeUnweighted graph store neighborWeighted graph store neighbor, weightAdjacency ListExampleUnweighted graph Weighted graphGraph Space RequirementsAdjacency matrix ½ N2 entries (for graph with N nodes, E edges) Many empty entries for large graphsCan implement as sparse arrayAdjacency listE edgesEach edge
View Full Document
Unlocking...