DEPTH FIRST TRAVERSAL Lesson Plan -2

Evocation

Traverse Graph All vertices in graph must to traverse A vertex in graph have multiple parents, traversal of graph have some problems not found in traversal of list and trees Two standard graph traversal Depth first traversal Breadth first traversal

Evocation

Depth First Traversal In depth first traversal, process all of vertex descendent before moving to adjacent vertex Process the first vertex of graph After processing first vertex, select any vertex adjacent to first vertex and process it As processing each vertex, select an adjacent vertex until reach a vertex with no adjacent entries

Depth First Traversal of a Tree A BCD EFGHI Depth First Traversal: A B E F C D G H I

Depth First Traversal of Graph

Push the first vertex A into stack Loop, pop the stack and after process the vertex, push all of adjacent vertices into stack To process X at step2, pop X from stack, process it and push G and H into stack, give the stack contents form step 3 When stack is empty, traversal is complete

DFS Example

Depth first Traversal Algorithm Algorithm depth First (graph) if (empty graph) return set walkptr to graph first loop (through all vertices) set processed to 0 end loop create stack (stack) loop (through vertex list) if (vertex not processed and not in stack) push stack( stack, walkptr ) set walkptr processed to 1 end if loop ( not empty stack(stack)) set vertex to pop stack(stack) process (vertex) set vertex to processed

Depth first Traversal Algorithm loop(through arc list) if(arc destination not in stack) push stack( stack, destination ) set destination to in stack end if get next destination end loop end if get next vertex end loop destroy stack (stack) end depth first

Mind Map Traverse Graph Depth First Traversal Breadth First Traversal DFS Example DFS Algorithm

Summary Graph must traverse all vertices Two standard graph traversal depth first and breadth first In depth first traversal, process all of vertex descendent before moving to adjacent vertex