Graphs & Graph AlgorithmsGraph Data StructuresGraph DefinitionsSlide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Graph OperationsBreadth-first Search (BFS)Slide 13Depth-first Search (DFS)Slide 15Traversal AlgorithmsTraversal – Avoid Revisiting NodesSlide 18Traversal Algorithm Using SetsTraversal Algorithm Using TagsBFS vs. DFS TraversalBFS Traversal AlgorithmDFS Traversal AlgorithmRecursive DFS AlgorithmGraphs & Graph Algorithms Fawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkGraph Data StructuresMany-to-many relationship between elementsEach element has multiple predecessorsEach element has multiple successorsGraph DefinitionsNodeElement of graphStateList of adjacent nodesEdgeConnection between two nodesStateEndpoints of edgeAGraph DefinitionsDirected graphDirected edgesUndirected graphUndirected edgesGraph DefinitionsWeighted graphWeight (cost) associated with each edgeGraph DefinitionsPath Sequence of nodes n1, n2, … nkEdge exists between each pair of nodes ni , ni+1ExampleA, B, C is a pathGraph DefinitionsPath Sequence of nodes n1, n2, … nkEdge exists between each pair of nodes ni , ni+1ExampleA, B, C is a pathA, E, D is not a pathGraph DefinitionsCyclePath that ends back at starting nodeExampleA, E, AGraph DefinitionsCyclePath that ends back at starting nodeExampleA, E, AA, B, C, D, E, ASimple pathNo cycles in pathAcyclic graphNo cycles in graphGraph DefinitionsReachablePath exists between nodesConnected graphEvery node is reachable from some node in graphUnconnected graphsGraph OperationsTraversal (search)Visit each node in graph exactly onceUsually perform computation at each nodeTwo approachesBreadth first search (BFS)Depth first search (DFS)Breadth-first Search (BFS)ApproachVisit all neighbors of node firstView as series of expanding circlesKeep list of nodes to visit in queueExample traversal1) n2) a, c, b3) e, g, h, i, j4) d, fBreadth-first Search (BFS)Example traversals12 34 5 6713 26 5 4712 35 6 47Left to right Right to left RandomDepth-first Search (DFS)ApproachVisit all nodes on path firstBacktrack when path endsKeep list of nodes to visit in a stackExample traversal1) n, a, b, c, d, …2) f …Depth-first Search (DFS)Example traversals12 63 5 7414 26 5 3712 64 3 75Left to right Right to left RandomTraversal AlgorithmsIssueHow to avoid revisiting nodesInfinite loop if cycles presentApproachesRecord set of visited nodesMark nodes as visited12 34 ? 5?Traversal – Avoid Revisiting NodesRecord set of visited nodesInitialize { Visited } to empty setAdd to { Visited } as nodes is visitedSkip nodes already in { Visited }1234V = 1234V = { 1 }1234V = { 1, 2 }Traversal – Avoid Revisiting NodesMark nodes as visitedInitialize tag on all nodes (to False)Set tag (to True) as node is visitedSkip nodes with tag = TrueFFFFTFFFTTFFTraversal Algorithm Using Sets{ Visited } = { Discovered } = { 1st node }while ( { Discovered } )take node X out of { Discovered }if X not in { Visited }add X to { Visited } for each successor Y of Xif ( Y is not in { Visited } )add Y to { Discovered }Traversal Algorithm Using Tagsfor all nodes Xset X.tag = False { 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)add Y to { Discovered }BFS vs. DFS TraversalOrder nodes taken out of { Discovered } keyImplement { Discovered } as Queue First in, first outTraverse nodes breadth first Implement { Discovered } as Stack First in, last outTraverse nodes depth firstBFS Traversal Algorithmfor all nodes XX.tag = False put 1st node in Queuewhile ( Queue not empty ) take node X out of Queueif (X.tag = False)set X.tag = Truefor each successor Y of Xif (Y.tag = False)put Y in QueueDFS Traversal Algorithmfor all nodes XX.tag = False put 1st node in Stackwhile (Stack not empty ) pop X off Stackif (X.tag = False)set X.tag = Truefor each successor Y of Xif (Y.tag = False)push Y onto StackRecursive DFS AlgorithmTraverse( ) for all nodes Xset X.tag = False Visit ( 1st node )Visit ( X )set X.tag = Truefor each successor Y of Xif (Y.tag = False)Visit ( Y
View Full Document
Unlocking...