Download to read offline
DFS & BFS in Computer Algorithm
- 1. BIRLA INSTITUTE OFTECHNOLOGY,MESRA JAIPUR CAMPUS TOPIC: DFS & BFS PRESENTED BY: SAJAN SINGH(MCA/25019/18) MEGHAJ KUMAR MALLICK(MCA/25017/18) MCA 2ND YEAR ,3RD SEMESTER
- 2. INTRODUCTION TO GRAPH •A graph G is simply a set V of vertices/nodes and a collection E of pairs of vertices from V, called edges/arcs. Vertices v={1,2,3,4,5} Edges={ (1,4), (1,2), (2,3), (3,5),(4,3) }
- 8.
- 9. BREATH FIRST SEARCH Search for all vertices that are directly reachable from root(called level 1 vertices). After mark all these vertices visit all these vertices that are directly reachable from level 1 vertices(called level2 vertices) and so on. In general k vertices are directly reachable from a level k-1 vertices.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15. APPLICATION OF BFS 1.Peer to peer networks: In peer to peer networks like BIT- Torrent, BFS search is used to find all neighbor nodes. 2. Social Networking Websites : In social networks, we can find people within a given distance ‘k’ from a person using BFS till ‘k’ levels . 2. In Garbage Collection: BFS is used in copying garbage collection
- 16. DEPTH FIRST SEARCH Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. It use the stack data structure (FILO) as frontier.
- 17.
- 18. DFS PROCEDURE Proceduredfs(s) make all vertices in graph as not reached invoke scan(s) Procedure scan(s) mark & visit s for each neighbor w of s if the neighbor is not reached invoke scan(w)
- 20. BFS & DFSCOMPARISON BFS DFS BFS stands for Breadth First Search. BFS can be done with the help of QUEUE i.e. FIFO. In BSF time & space complexity is lesser as there is no need to do backtracking. BFS is slower than DFS. BFS requires more memory. It is useful in finding shortest path DFS stands for Depth First Search. DFS can be done using STACK i.e. LIFO It has higher time & space complexity due to backtracking. DFS is faster than BFS DFS requires less memory. Not useful for shortest path.
- 21.