What Is DFS (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 (top) node of a tree and goes as far as it can down a given branch (path), then backtracks until it finds an unexplored path, and then explores it. The algorithm does this until the entire graph has been explored.
Depth First Search (DFS) are normally used as subroutines in other more complex algorithms. Hopcroft-Karp, tree-traversal and matching algorithm are examples of algorithm that use DFS to find a matching in a graph.
What Is BFS (Breadth First Search)
Breadth First search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Breadth First Search (BFS) is an important search algorithm that is used to solve many problems including finding the shortest path in graph and solving puzzle games (such as Rubik’s Cubes). In computer science, it can also be used to solve graph problems such as analyzing networks, mapping routes and scheduling.
DFS (Depth First Search) Features
- DFS starts the traversal from the root node and explore the search as far as possible from the root node i.e depth wise.
- DFS algorithm works in two stages. In the first stage, the visited vertices are pushed onto the stack and later on when there is no vertex further to visit those that are popped-off.
- DFS search can be done with the help of stack i.e LIFO implementations.
- DFS is not useful in finding shortest path. It is used to perform a traversal of general graph and the idea of DFS is to make a path as long as possible and then go back (backtrack) to add branches also as long as possible.
- DFS is comparatively faster when compared to BFS.
- The time complexity of DFS is O(V+E) where V stands for vertices and E stands for edges.
- DFS requires comparatively less memory to BFS.
- Some Applications of DFS include: Topological sorting, Finding connected components, Finding articulation points (cut vertices) of the graph, Solving puzzles such as maze and Finding strongly connected components.
BFS (Breadth First Search) Features
- BFS starts traversal from the root node and then explore the search in the level by level manner i.e as close as possible from the root node.
- BFS algorithm works in a single stage. The visited vertices are removed from the queue and then displayed at once.
- BFS can be done with the help of queue i.e FIFO implementation.
- BFS is useful in finding shortest path. BFS can be used to find the shortest distance between some starting node and the remaining nodes of the graph.
- BFS is comparatively slower when compared to DFS.
- The time complexity of BFS is O(V+E) where V stands for vertices and E stands for edges.
- BFS requires comparatively more memory to DFS.
- Some applications of BFS include:Finding connected components in a graph, Testing a graph for bipartiteness, Finding all nodes within one connected component and Finding the shortest path between two nodes.
Difference Between DFS And BFS In Tabular Form
BASIS OF COMPARISON | DFS | BFS |
It starts the traversal from the root node and explores the search as far as possible from the root node i.e depth wise. | BFS starts traversal from the root node and then explore the search in the level by level manner i.e as close as possible from the root node. | |
Stages Of Algorithm Working | Algorithm works in two stages. In the first stage, the visited vertices are pushed onto the stack and later on when there is no vertex further to visit those that are popped-off. | Algorithm works in a single stage. The visited vertices are removed from the queue and then displayed at once. |
Search | Its search can be done with the help of stack i.e LIFO implementations. | Its search can be done with the help of queue i.e FIFO implementation. |
Usefulness | It is not useful in finding shortest path. It is used to perform a traversal of general graph and the idea of DFS is to make a path as long as possible and then go back (backtrack) to add branches also as long as possible. | It is useful in finding shortest path. BFS can be used to find the shortest distance between some starting node and the remaining nodes of the graph. |
Speed | It is comparatively faster when compared to BFS. | It is comparatively slower when compared to DFS. |
Time Complexity | The time complexity of BFS is O(V+E) where V stands for vertices and E stands for edges. | The time complexity of BFS is O(V+E) where V stands for vertices and E stands for edges. |
Memory Requirement | DFS requires comparatively less memory to BFS. | It requires comparatively more memory to DFS. |
Application | Topological sorting Finding connected components Finding articulation points (cut vertices) of the graph.Solving puzzles such as maze. Finding strongly connected components. | Finding connected components in a graph Testing a graph for bipartiteness Finding all nodes within one connected component. Finding the shortest path between two nodes |