Downloaded 128 times
Uploaded byRajandeep Gill
Graph traversal-BFS & DFS
The document discusses graph traversal algorithms depth-first search (DFS) and breadth-first search (BFS). DFS uses a stack and visits nodes by traversing as deep as possible before backtracking. BFS uses a queue and visits all nodes at each level from the starting node before moving to the next level. Examples are given applying DFS and BFS to a sample graph. Applications of DFS and BFS are also listed such as computing distances, checking for cycles/bipartiteness, and topological sorting.
In this document
Powered by AI
Introduces Depth-First Search (DFS) and Breadth-First Search (BFS) methods, their goals and characteristics. Highlights tree structure and traversal types.
Details recursive DFS method with code and examples, showing node visitation order starting from Node 5 using stack operations.
Explains BFS concept, likening it to ripples in a pond, along with the implementation of BFS in code.
Illustrates step-by-step execution of BFS starting at Node 5, showing how adjacent nodes are visited systematically.
Discusses various applications of BFS, including computing distances, cycle detection, bipartiteness, and reachability.
Explores applications of DFS, such as computing strongly connected components, checking for biconnected graphs, and topological ordering.
Graph traversal-BFS & DFS
- 1. Graph Traversal Depth-First Search •Using Stack Breadth-First Search • Using Queue
- 2. Overview • Goal – Tosystematically visit the nodes of a graph • A tree is a directed, acyclic, graph (DAG) • If the graph is a tree, – DFS is exhibited by preorder, postorder, and (for binary trees) inorder traversals – BFS is exhibited by level-order traversal
- 3. Depth-First Search // recursive,preorder, depth-first search 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
- 4. Example 0 7 1 5 4 3 2 6 Policy: Visit adjacentnodes in increasing index order
- 5. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 2 7 6 4
- 6. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 Push 5
- 7. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 Pop/Visit/Mark 5
- 8. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 2 Push 2, Push 1
- 9. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 2 Pop/Visit/Mark 1
- 10. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 4 2 Push 4, Push 0
- 11. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 4 2 Pop/Visit/Mark 0
- 12. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 4 2 Push 7, Push 3
- 13. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 4 2 Pop/Visit/Mark 3
- 14. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 4 2 2 is already in stack
- 15. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 7 4 2 Pop/Mark/Visit 7
- 16. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 6 4 2 Push 6
- 17. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 6 4 2 Pop/Mark/Visit 6
- 18. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 6 4 2 Pop/Mark/Visit 4
- 19. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 6 4 2 Pop/Mark/Visit 2
- 20. DFS: Start withNode 5 0 7 1 5 4 3 2 6 5 1 0 3 7 6 4 2 Done
- 21. Breadth-first Search • Ripplesin a pond • Visit designated node • Then visited unvisited nodes a distance i away, where i = 1, 2, 3, etc. • For nodes the same distance away, visit nodes in systematic manner (eg. increasing index order)
- 22. 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
- 23. BFS: Start withNode 5 7 1 5 4 3 2 6 0
- 24. BFS: Start withNode 5 7 1 5 4 3 2 6 0 5
- 25.
- 26. BFS: Visit 1and add its adjacent nodes 7 1 5 4 3 2 6 5 1 0 5 1 2 0 4
- 27. BFS: Visit 2and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 5 1 2 0 4
- 28. BFS: Visit 0and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 0 5 1 2 0 4 3 7
- 29. BFS: Visit 4and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 4 0 5 1 2 0 4 3 7
- 30. BFS: Visit 3and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 4 3 0 5 1 2 0 4 3 7
- 31. BFS: Visit 7and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 4 3 7 0 5 1 2 0 4 3 7 6
- 32. BFS: Visit 6and add its adjacent nodes 7 1 5 4 3 2 6 5 1 2 0 4 3 7 6 0 5 1 2 0 4 3 7 6
- 33. BFS Traversal Result 7 1 5 4 3 2 6 51 2 0 4 3 7 6 0
- 34. Applications of BFS •Computing Distances: Given a source vertex x, compute the distance of all vertices from x. • Checking for cycles in a graph: Given an undirected graph G, report whether there exists a cycle in the graph or not. (Note: won’t work for directed graphs) • Checking for bipartite graph: Given a graph, check whether it is bipartite or not? A graph is said to be bipartite if there is a partition of the vertex set V into two sets V1 and V2 such that if two vertices are adjacent, either both are in V1 or both are in V2. • Reachability: Given a graph G and vertices x and y, determine if there exists a path from x to y.
- 35. Applications of DFS •Computing Strongly Connected Components: A directed graph is strongly connected if there exists a path from every vertex to every other vertex. Trivial Algo: Perform DFS n times. Efficient Algo: Single 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. • Topological Ordering: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge (x, y), vertex x comes before y in the ordering