Breadth First Search (BFS)
Breadth First Search algorithm used in
Like depth first search, BFS traverse a connected component of a given graph and defines a spanning tree.
Algorithm Breadth First Search
BFS starts at a given vertex, which is at level 0. In the first stage, we visit all vertices at level 1. In the second stage, we visit all vertices at second level. These new vertices, which are adjacent to level 1 vertices, and so on. The BFS traversal terminates when every vertex has been visited.
BREADTH FIRST SEARCH (G, S)
Input: A graph G and a vertex.
Output: Edges labeled as discovery and cross edges in the connected component.Create a Queue Q.
ENQUEUE (Q, S) // Insert S into Q.
While Q is not empty do
for each vertex v in Q do
for all edges e incident on v do
if edge e is unexplored then
let w be the other endpoint of e.
if vertex w is unexpected then
- mark e as a discovery edge
- insert w into Q
else
mark e as a cross edge
BFS label each vertex by the length of a shortest path (in terms of number of edges) from the start vertex.
Step1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Step 9
Starting vertex (node) is S
Solid edge = discovery edge.
Dashed edge = error edge (since none of them connects a vertex to one of its ancestors).
As with the depth first search (DFS), the discovery edges form a spanning tree, which in this case we call the BSF-tree.
BSF used to solve following problem
Testing whether graph is connected.
Computing a spanning forest of graph.
Computing, for every vertex in graph, a path with the minimum number of edges between start vertex and current vertex or reporting that no such path exists.
Computing a cycle in graph or reporting that no such cycle exists.
Analysis
Total running time of BFS is O(V + E).
We define bipartite graph as follows: A bipartite graph is an undirected graph G = (V, E) in which V
can be partitioned into two sets V1 and V2 such that (u,
v) Î E
implies either u 
V1
and v V2
or u V2
and v V1.
That is, all edges go between the two sets V1 and V2.
In other to determine if a graph G = (V, E) is bipartite, we perform a BFS on
it with a little modification such that whenever the BFS is at a vertex
u and
encounters a vertex v that is already 'gray' our modified BSF should
check to see if the depth of both u and
v are even, or if they are
both odd. If either of these conditions holds which implies
d[u] and d[v]
have the same parity, then the graph is not bipartite. Note that this
modification does not change the running time of BFS and remains
(V + E).
Formally, to check if the given graph is bipartite, the algorithm traverse the graph labeling the vertices 0, 1, or 2 corresponding to unvisited., partition 1 and partition 2 nodes. If an edge is detected between two vertices in the same partition, the algorithm returns.
ALGORITHM: BIPARTITE (G, S)
For each vertex U Î V[G] - {s} do
Color[u] = WHITE
d[u] = ∞
partition[u] = 0Color[s] = gray
partition[s] = 1
d[s] = 0
Q = [s]
While Queue 'Q' is not empty do
u = head [Q]
for each v in Adj[u] do
if partition [u] = partition [v] then
return 0
else
if color[v] WHITE then
color[v] = gray
d[v] = d[u] +1
partition[v] = 3 - partition[u]
ENQUEUE (Q, v)
DEQUEUE (Q)
Color[u] = BLACK
Return 1
As Bipartite (G, S) traverse the graph it labels the vertices with a partition number consisted with the graph being bipartite. If at any vertex, algorithm detects an inconsistency, it shows with an invalid return value,. Partition value of u will always be a valid number as it was enqueued at some point and its partition was assigned at that point. AT line 19, partition of v will unchanged if it already set, otherwise it will be set to a value opposite to that of vertex u.
The lines added to BFS algorithm take constant time to execute and so the running time is the same as that of BFS which is O(V + E).
Diameter of Tree
The diameter of a tree T = (V, E) is the largest of all shortest-path distance in the tree and given by max[dist(u,v)]. As we have mentioned that BSF can be use to compute, for every vertex in graph, a path with the minimum number of edges between start vertex and current vertex. It is quite easy to compute the diameter of a tree. For each vertex in the tree, we use BFS algorithm to get a shortest-path. By using a global variable length, we record the largest of all shortest-paths. This will clearly takes O(V(V + E)) time.
ALGORITHM: TREE_DIAMETER (T)
maxlength = 0
For S = 0 to S < |V[T]|
temp = BSF(T, S)
if maxlength < temp
maxlength = temp
Increment s by 1
return maxlength
