Breadth-first search is one of the simplest algorithms for searching a graph and the important concept for many important graph algorithms. Dijkstra's single-source shortest-paths algorithm and Prim's minimum-spanning-tree algorithm use ideas similar to those in breadth-first search.
Given a graph G = (V, E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to "discover" every vertex that is reachable from s. It computes the distance (fewest number of edges) from s to all such reachable vertices. It also produces a "breadth-first tree" with root s that contains all such reachable vertices. For any vertex v reachable from s, the path in the breadth-first tree from s to v corresponds to a "shortest path" from s to v in G, that is, a path containing the fewest number of edges. The algorithm works on both directed and undirected graphs.
A queue is used to
perform Breadth First Search. Algorithm starts from a source node and goes on
finding the adjacent nodes adding nodes to the queue and pop the visited nodes.
The BFS sequence for the given graph is : s,w,r,t,x,v,u,y.
No comments:
Post a Comment