What is BFS? (Graph Algorithm)
What is the Breadth First Search algorithm?
https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/
The last time, I talked about the Depth First Search (DFS) algorithm for traversing a graph.
One other famous graph algorithm is the Breadth First Search (a.k.a BFS).
Unlike the DFS algorithm that gets through the nodes as far as possible until it reaches the unvisited connected node, the BFS algorithm visits all nodes at the same level before moving on to the next level.
The advantage of using the BFS algorithm is that it "can be used to find a single source shortest path in an unweighted graph because, in BFS, we reach a vertex with a minimum number of edges from a source vertex."
For the BFS, it requires to use of the "queue" data structure to save nodes at the same level.
The time complexity of the BFS algorithm is O(V + E) where V is the number of vertexes and E is the number of edges.
Down below is an example C++ implementation of the BFS algorithm:
References:
https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/
https://www.educative.io/answers/what-is-breadth-first-search
Comments
Post a Comment