| Breadth First Search (BFS) | Depth First Search (DFS) |
|---|---|
| Queue data structure is used for breadth first search implementation. | Stack data structure is used for depth first search implementation. |
| It computes shortest path from source to every another node. | It computes number of connected components in undirected graph.It can also be used to determine whether a graph is acyclic or not. |
| Start node is given. | No start node is given. |
| It generates predecer tree. | It generates predecer forest. |
| In an unweighted graph performing breadth first search starting from source node takes O(n) time if graph contains n vertices. | Discovery time is less than finishing time. |
No comments:
Post a Comment