Let us tackle with the fear of BFS and DFS.
While both BFS and DFS are algorithms for traversing or searching tree or graph data structures. Let us dive into more details about their implementation, applications and time complexity.
BFS
Input Graph:
Output in BFS: ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"]
What is BFS:
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Implementation for BFS:
Time Complexity of BFS:
The time complexity can be expressed as O(|V|+|E|), since every vertex and every edge will be explored in the worst case. |V| is the number of vertices and |E| is the number of edges in the graph. Note that O(|E|) may vary between O(1) and O(|V|^{2}), depending on how sparse the input graph is.
When the number of vertices in the graph is known ahead of time, and additional data structures are used to determine which vertices have already been added to the queue, the space complexity can be expressed as O(|V|), where |V| is the number of vertices. This is in addition to the space required for the graph itself, which may vary depending on the graph representation used by an implementation of the algorithm.
Why and where BFS is used:
1) Shortest Path and Minimum Spanning Tree for unweighted graph In an unweighted graph, the shortest path is the path with least number of edges. With Breadth First, we always reach a vertex from given source using the minimum number of edges. Also, in case of unweighted graphs, any spanning tree is Minimum Spanning Tree and we can use either Depth or Breadth first traversal for finding a spanning tree.
2) Peer to Peer Networks. In Peer to Peer Networks like Torrent, Breadth First Search is used to find all neighbour nodes.
3) Crawlers in Search Engines: Crawlers build index using Breadth First. The idea is to start from source page and follow all links from source and keep doing same. Depth First Traversal can also be used for crawlers, but the advantage with Breadth First Traversal is, depth or levels of the built tree can be limited.
4) Social Networking Websites: In social networks, we can find people within a given distance ‘k’ from a person using Breadth First Search till ‘k’ levels.
DFS
Input Graph:
Output in DFS: ["A", "B", "E", "F", "I", "J", "C", "D", "G", "K", "H"]
Why and where DFS is used?
1) For a weighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.
2) Detecting cycle in a graph
A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges.
3) Path Finding
We can specialise the DFS algorithm to find a path between two given vertices u and z.
i) Call DFS(G, u) with u as the start vertex.
ii) Use a stack S to keep track of the path between the start vertex and the current vertex.
iii) As soon as destination vertex z is encountered, return the path as the
contents of the stack
- https://en.wikipedia.org/wiki/Breadth-first_search
- https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
- https://www.geeksforgeeks.org/applications-of-breadth-first-traversal/
- https://www.geeksforgeeks.org/applications-of-depth-first-search/
- https://www.youtube.com/watch?v=zaBhtODEL0w
- https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/
No comments:
Post a Comment