Graph traversal in Data structure with example

graph traversal in design and analysis of algorithms and graph traversal program in java
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
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 © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Graph traversals 2 Outline We will look at traversals of graphs – Breadth-first or depth-first traversals – Must avoid cycles – Depth-first 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 breadth-first or depth-first traversals – Breadth-first requires a queue – Depth-first 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 Breadth-first traversal Consider implementing a breadth-first 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 depth-first traversal An implementation can use a queue void Graph::depth_first_traversal( Vertex first ) const unordered_mapVertex , 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 : v-adjacent_vertices() ) if ( hash.member( w ) ) hash.insert( w ); queue.push( w ); Graph traversals 6 Breadth-first traversal The size of the queue is O(V) – The size depends both on: • The number of edges, and • The out-degree of the verticesGraph traversals 7 Depth-first traversal Consider implementing a depth-first 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 depth-first traversal A recursive implementation uses the call stack for memory: void Graph::depth_first_traversal( Vertex first ) const std::unordered_mapVertex , int hash; hash.insert( first ); first-depth_first_traversal( hash ); void Vertex::depth_first_traversal( unordered_mapVertex , int &hash ) const // Perform an operation on this for ( Vertex v : adjacent_vertices() ) if ( hash.member( v ) ) hash.insert( v ); v-depth_first_traversal( hash ); Graph traversals 9 Iterative depth-first traversal An iterative implementation can use a stack void Graph::depth_first_traversal( Vertex first ) const unordered_mapVertex , 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 : v-adjacent_vertices() ) if ( hash.member( w ) ) hash.insert( w ); stack.push( w ); Graph traversals 10 Iterative depth-first 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 object-oriented 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 auto-increment operator would pop the top of the stack and place any unvisited adjacent vertices onto the stack/queue – The auto-decrement operator would not be implemented • You can’t go back…Graph traversals 12 Example Consider this graphGraph traversals 13 Example Performing a breadth-first traversal – Push the first vertex onto the queue AGraph traversals 14 Example Performing a breadth-first traversal – Pop A and push B, C and E A B C EGraph traversals 15 Example Performing a breadth-first traversal: – Pop B and push D A, B C E DGraph traversals 16 Example Performing a breadth-first traversal: – Pop C and push F A, B, C E D FGraph traversals 17 Example Performing a breadth-first traversal: – Pop E and push G and H A, B, C, E D F G HGraph traversals 18 Example Performing a breadth-first traversal: – Pop D A, B, C, E, D F G HGraph traversals 19 Example Performing a breadth-first traversal: – Pop F A, B, C, E, D, F G HGraph traversals 20 Example Performing a breadth-first traversal: – Pop G and push I A, B, C, E, D, F, G H I