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 (s) 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