Question? Leave a message!




Graph traversals

Graph traversals
ECE 250 Algorithms and Data Structures Graph traversals Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Graph traversals 2 Outline We will look at traversals of graphs – Breadthfirst or depthfirst traversals – Must avoid cycles – Depthfirst traversals can be recursive or iterative – Problems that can be solved using traversalsGraph traversals 3 Strategies Traversals of graphs are also called searches We can use either breadthfirst or depthfirst traversals – Breadthfirst requires a queue – Depthfirst requires a stack We each case, we will have to track which vertices have been visited requiring Q(V) memory – One option is a hash table – If we can use a bit array, this requires only V/8 bytes The time complexity cannot be better than and should not be worse than Q(V + E) – Connected graphs simplify this to Q(E) 2 – Worst case: Q(V )Graph traversals 4 Breadthfirst traversal Consider implementing a breadthfirst traversal on a graph: – Choose any vertex, mark it as visited and push it onto queue – While the queue is not empty: • Pop to top vertex v from the queue • For each vertex adjacent to v that has not been visited: – Mark it visited, and – Push it onto the queue This continues until the queue is empty – Note: if there are no unvisited vertices, the graph is connected,Graph traversals 5 Iterative depthfirst traversal An implementation can use a queue void Graph::depthfirsttraversal( Vertex first ) const unorderedmapVertex , int hash; hash.insert( first ); std::queueVertex queue; queue.push( first ); while ( queue.empty() ) Vertex v = queue.front(); queue.pop(); // Perform an operation on v for ( Vertex w : vadjacentvertices() ) if ( hash.member( w ) ) hash.insert( w ); queue.push( w ); Graph traversals 6 Breadthfirst traversal The size of the queue is O(V) – The size depends both on: • The number of edges, and • The outdegree of the verticesGraph traversals 7 Depthfirst traversal Consider implementing a depthfirst traversal on a graph: – Choose any vertex, mark it as visited – From that vertex: • If there is another adjacent vertex not yet visited, go to it • Otherwise, go back to the most previous vertex that has not yet had all of its adjacent vertices visited and continue from there – Continue until no visited vertices have unvisited adjacent vertices Two implementations: – Recursive – IterativeGraph traversals 8 Recursive depthfirst traversal A recursive implementation uses the call stack for memory: void Graph::depthfirsttraversal( Vertex first ) const std::unorderedmapVertex , int hash; hash.insert( first ); firstdepthfirsttraversal( hash ); void Vertex::depthfirsttraversal( unorderedmapVertex , int hash ) const // Perform an operation on this for ( Vertex v : adjacentvertices() ) if ( hash.member( v ) ) hash.insert( v ); vdepthfirsttraversal( hash ); Graph traversals 9 Iterative depthfirst traversal An iterative implementation can use a stack void Graph::depthfirsttraversal( Vertex first ) const unorderedmapVertex , int hash; hash.insert( first ); std::stackVertex stack; stack.push( first ); while ( stack.empty() ) Vertex v = stack.top(); stack.pop(); // Perform an operation on v for ( Vertex w : vadjacentvertices() ) if ( hash.member( w ) ) hash.insert( w ); stack.push( w ); Graph traversals 10 Iterative depthfirst traversal If memory is an issue, we can reduce the stack size: – For the vertex: • Mark it as visited • Perform an operation on that vertex • Place it onto an empty stack – While the stack is not empty: • If the vertex on the top of the stack has an unvisited adjacent vertex, – Mark it as visited – Perform an operation on that vertex – Place it onto the top of the stack • Otherwise, pop the top of the stackGraph traversals 11 Standard Template Library (STL) approach An objectoriented STL approach would be create a iterator class: – The hash table and stack/queue are private member variables created in the constructor – Internally, it would store the current node – The autoincrement operator would pop the top of the stack and place any unvisited adjacent vertices onto the stack/queue – The autodecrement operator would not be implemented • You can’t go back…Graph traversals 12 Example Consider this graphGraph traversals 13 Example Performing a breadthfirst traversal – Push the first vertex onto the queue AGraph traversals 14 Example Performing a breadthfirst traversal – Pop A and push B, C and E A B C EGraph traversals 15 Example Performing a breadthfirst traversal: – Pop B and push D A, B C E DGraph traversals 16 Example Performing a breadthfirst traversal: – Pop C and push F A, B, C E D FGraph traversals 17 Example Performing a breadthfirst traversal: – Pop E and push G and H A, B, C, E D F G HGraph traversals 18 Example Performing a breadthfirst traversal: – Pop D A, B, C, E, D F G HGraph traversals 19 Example Performing a breadthfirst traversal: – Pop F A, B, C, E, D, F G HGraph traversals 20 Example Performing a breadthfirst traversal: – Pop G and push I A, B, C, E, D, F, G H IGraph traversals 21 Example Performing a breadthfirst traversal: – Pop H A, B, C, E, D, F, G, H IGraph traversals 22 Example Performing a breadthfirst traversal: – Pop I A, B, C, E, D, F, G, H, IGraph traversals 23 Example Performing a breadthfirst traversal: – The queue is empty: we are finished A, B, C, E, D, F, G, H, IGraph traversals 24 Example Perform a recursive depthfirst traversal on this same graphGraph traversals 25 Example Performing a recursive depthfirst traversal: – Visit the first node AGraph traversals 26 Example Performing a recursive depthfirst traversal: – A has an unvisited neighbor A, BGraph traversals 27 Example Performing a recursive depthfirst traversal: – B has an unvisited neighbor A, B, CGraph traversals 28 Example Performing a recursive depthfirst traversal: – C has an unvisited neighbor A, B, C, DGraph traversals 29 Example Performing a recursive depthfirst traversal: – D has no unvisited neighbors, so we return to C A, B, C, D, EGraph traversals 30 Example Performing a recursive depthfirst traversal: – E has an unvisited neighbor A, B, C, D, E, GGraph traversals 31 Example Performing a recursive depthfirst traversal: – F has an unvisited neighbor A, B, C, D, E, G, IGraph traversals 32 Example Performing a recursive depthfirst traversal: – H has an unvisited neighbor A, B, C, D, E, G, I, HGraph traversals 33 Example Performing a recursive depthfirst traversal: – We recurse back to C which has an unvisited neighbour A, B, C, D, E, G, I, H, FGraph traversals 34 Example Performing a recursive depthfirst traversal: – We recurse finding that no other nodes have unvisited neighbours A, B, C, D, E, G, I, H, FGraph traversals 35 Comparison Performing a recursive depthfirst traversal: – We recurse finding that no other nodes have unvisited neighbours A, B, C, D, E, G, I, H, FGraph traversals 36 Comparison The order in which vertices can differ greatly – An iterative depthfirst traversal may also be different again A, B, C, E, D, F, G, H, I A, B, C, D, E, G, I, H, FGraph traversals 37 Applications Applications of tree traversals include: – Determining connectiveness and finding connected subgraphs – Determining the path length from one vertex to all others – Testing if a graph is bipartite – Determining maximum flow – Cheney’s algorithm for garbage collectionGraph traversals 38 Summary This topic covered graph traversals – Considered breadthfirst and depthfirst traversals – Depthfirst traversals can recursive or iterative – More overhead than traversals of rooted trees – Considered a STL approach to the design – Considered an example with both implementations – They are also called searchesGraph traversals 39 References Wikipedia, http://en.wikipedia.org/wiki/Graphtraversal http://en.wikipedia.org/wiki/Depthfirstsearch http://en.wikipedia.org/wiki/Breadthfirstsearch These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017