DEPTH FIRST TRAVERSAL Lesson Plan -2. Evocation Traverse Graph All vertices in graph must to traverse A vertex in graph have multiple parents, traversal. - презентация

1 DEPTH FIRST TRAVERSAL Lesson Plan -2

2 Evocation

3 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

4 Evocation

5 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

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

7 Depth First Traversal of Graph

8 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

9 DFS Example

10

11

12

13

14

15

16

17

18 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

19 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

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

21 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