BFS & DFS in Data Structure

This is an PPT of Data Structure. It include the following topic "BFS & DFS in Data Structure".

1. BFS AND DFS Presented By: Muskaan MCA/25020/18

2. CONTENTS Introduction Types of graph Traversal Depth-First Search Breadth-First Search Application of BFS and DFS

3. INTRODUCTION Graph traversal   is also known as  graph  search refers to the process of visiting each vertex in a  graph . Such  traversals  are classified by the order in which the vertices are visited. Tree  traversal  is a special case of  graph traversal .

4. DEPTH FIRST SEARCH Depth-first search ( DFS ) is an algorithm for traversing or searching tree or graph data structures. DFS uses stack.

5. Depth-First Search // recursive, preorder void dfs (Node v) { if (v == null) return; if (v not yet visited) visit&mark(v); // visit node before adjacent nodes for (each w adjacent to v) if (w has not yet been visited) dfs(w); } // dfs

6. E xa m p le 7 1 5 4 3 2 6 Policy: Visit adjacent nodes in increasing index order

7. DFS: Start with Node 5 7 1 5 4 3 2 6 5 1 0 3 2 7 6 4

8. DFS: Start with Node 5 7 1 5 4 3 2 6 5 Push 5

9. DFS: Start with Node 5 7 1 5 4 3 2 6 Pop/Visit/Mark 5 5

10. DFS: Start with Node 5 7 1 5 4 3 2 6 1 2 5 Push 2, Push 1

11. DFS: Start with Node 5 7 1 5 4 3 2 6 2 Pop/Visit/Mark 1 5 1

12. DFS: Start with Node 5 7 1 5 4 3 2 6 4 2 5 1 Push 4, Push

13. DFS: Start with Node 5 7 1 5 4 3 2 6 4 2 5 1 0 Pop/Visit/Mark

14. DFS: Start with Node 5 7 1 5 4 3 2 6 3 7 4 2 Push 7, Push 3 5 1 0

15. DFS: Start with Node 5 7 1 5 4 3 2 6 7 4 2 5 1 0 3 Pop/Visit/Mark 3

16. DFS: Start with Node 5 7 1 5 4 3 2 6 7 4 2 5 1 0 3 2 is already in stack

17. DFS: Start with Node 5 7 1 5 4 3 2 6 7 4 2 Pop/Mark/Visit 7 5 1 0 3 7

18. DFS: Start with Node 5 7 1 5 4 3 2 6 6 4 2 5 1 0 3 7 Push 6

19. DFS: Start with Node 5 7 1 5 4 3 2 6 4 2 5 1 0 3 7 6 Pop/Mark/Visit 6

20. DFS: Start with Node 5 7 1 5 4 3 2 6 2 Pop/Mark/Visit 4 5 1 0 3 7 6 4

21. DFS: Start with Node 5 7 1 5 4 3 2 6 Pop/Mark/Visit 2 5 1 0 3 7 6 4 2

22. DFS: Start with Node 5 7 1 5 4 3 2 6 D on e 5 1 0 3 7 6 4 2

23. BREADTH FIRST SEARCH Breadth-first search  ( BFS ) is an  algorithm  for traversing or searching  tree  or  graph  data structures. It uses queue.

24. Breadth-First Search // non-recursive, preorder, breadth-first search void bfs (Node v) { if (v == null) return; enqueue(v); while (queue is not empty) { dequeue(v); if (v has not yet been visited) mark&visit(v); for (each w adjacent to v) if (w has not yet been visited && has not been queued) enqueue(w); } // while } // bfs

25. BFS: Start with Node 5 7 1 5 4 3 2 6

26. BFS: Start with Node 5 7 1 5 4 3 2 6 5

27. BFS: Node one-away 7 1 5 4 3 2 6 5 5 1 2

28. BFS: Visit 1 and add its adjacent nodes 7 1 5 4 3 2 6 5 1 5 1 2 4

29. BFS: Visit 2 and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 5 1 2 4

30. BFS: Visit 0 and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 5 1 2 4 3 7

31. BFS: Visit 4 and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 4 5 1 2 4 3 7

32. BFS: Visit 3 and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 4 3 5 1 2 4 3 7

33. BFS: Visit 7 and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 4 3 7 5 1 2 4 3 7 6

34. BFS: Visit 6 and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 4 3 7 6 5 1 2 4 3 7 6

35. BFS Traversal Result 7 1 5 4 3 2 6 5 1 2 0 4 3 7 6

36. Ap p l ic a t i ons of B FS • • • Computing Distances Checking for cycles in a graph Reachability : Given a graph G and vertices x and y , determine if there exists a path from x to y .

37. A pp l i c a t i ons of DFS • Checking for Biconnected Graph : A graph is biconnected if removal of any vertex does not affect connectivity of the other vertices. Used to test if network is robust to failure of certain nodes. A single DFS traversal algorithm .