Graphs & Graph Algorithms 2OverviewGraph ImplementationAdjacency MatrixSlide 5Slide 6Adjacency ListSlide 8Adjacency Set/MapGraph Space RequirementsGraph Time RequirementsSpanning TreeRecursive Spanning Tree ConstructionSpanning Tree ConstructionBreadth & Depth First Spanning TreesDepth-First Spanning Tree ExampleBreadth-First Spanning Tree ExampleSlide 18Minimum Spanning Tree (MST)Algorithms for MSTShortest Path – Djikstra’s AlgorithmMST – Prim’s AlgorithmMST – Kruskal’s AlgorithmMST – Kruskal’s Algorithm ExampleSlide 25MST – Connected Subgraph ExampleSlide 27Union find algorithm/data structureHow fast is it?Inverse Ackermann’s functionGraphs & Graph Algorithms 2 Nelson Padua-PerezBill PughDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewGraph implementationAdjacency list / matrix / setSpanning treesMinimum spanning treePrim’s algorithmKruskal’s algorithmGraph ImplementationHow do we represent edges?Adjacency matrix2D array of neighborsAdjacency listlist of neighborsAdjacency set/mapImportant 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 or array list for each node of neighbors/successorsfor directed graph, may need predecessors as wellUnweighted graph store neighborWeighted graph store neighbor, weightAdjacency ListExampleUnweighted graph Weighted graphAdjacency Set/MapFor each edge, store a Set or Map of neighbors/successorsfor directed graphs, may need separate Map for predecessorsFor unweighted graphs, use a SetFor weighted graphs, use a Map from nodes to weightsGraph Space RequirementsAdjacency matrix ½ N2 entries (for graph with N nodes, E edges) Many empty entries for large graphsAdjacency listE entriesAdjacency Set/MapE entriesSpace overhead per entry higher than for adjacency listGraph Time RequirementsAverage Complexity of operationsFor graph with N nodes, E edgesOperation Adj Matrix Adj List Adj Set/MapFind edge O(1) O(E/N) O(1)Insert edge O(1) O(E/N) O(1)Delete edge O(1) O(E/N) O(1)Enumerate edgesO(N) O(E/N) O(E/N)Spanning 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 traversalRecursive Spanning Tree ConstructionKnown = { 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)Spanning Tree ConstructionKnown = { 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 KnownBreadth & Depth First Spanning TreesBreadth-first Depth-firstDepth-First Spanning Tree ExampleBreadth-First Spanning Tree ExampleSpanning Tree ConstructionMultiple 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 treesMinimum Spanning Tree (MST)Spanning tree with minimum total edge weight Multiple MSTs possible (with same weight)Algorithms for MSTTwo well known algorithms for minimum spanning treedeveloped independentlyPrim’s algorithmdescribed in bookKruskal’s algorithmNot Clyde Kruskal (prof in our department, but his uncle)Shortest Path – Djikstra’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 algorithmMST – 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] = KOptimal solution computed with greedy algorithmMST – 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?Traversal approachTraverse tree starting at XIf we can reach Y, adding (X,Y) would create cycleConnected 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 cycleOtherwiseWe can add edge (X,Y) to spanning tree Merge sets containing X, Y (single subgraph)MST – Connected Subgraph ExampleMST – Connected Subgraph ExampleUnion find algorithm/data structureAlgorithm and data structure that allows you to ask this question.Start with n nodes, each in different subgraphsTwo operations:Are nodes x and y in the same subgraph?Merge the subgraphs containing x and yHow fast is it?Ackermann’s functionint 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(2,2) = 7A(3,3) = 61A(4,2) = 265536 - 3A(4,3) = 2265536 - 3 A(4,4) = 22265536 - 3Inverse Ackermann’s function(n) is the inverse Ackermann’s function(n) = the smallest k s.t. A(k,k) >= n(number of atoms in universe) = 4A sequence of n operations on a union find data structure requires O(n (n) )
View Full Document
Unlocking...