GRAPH TRAVERSALS - BREADTH FIRST
SEARCH WORKING PRINCIPLE:
1. It starts
from the arbitrary vertex
2. It visits
all vertices adjacent to starting vertex.
3. Then all
unvisited vertices between two edjes apart from it.
4. If there still remain unvisited vertices, the algorithm has to be restarted at an arbitrary vertex of another connected component of the graph.
♦ Queue is
used to trace BFS.
♦ The queue
is initialized with the traversal's starting vertex, which is marked as
visited. ♦ On each iteration, the algorithm identifies all unvisited vertices
that are adjacent to the front vertex, marks them as visited, and adds them to
the queue; after that, the front vertex is removed from the queue.
1. BREADTH FIRST SEARCH FOREST
♦ Similarly
to a DFS traversal, it is useful to accompany a BFS traversal by constructing
the so-called breadth-first search
forest.
1.
The traversal's starting vertex serves as the root
of the first tree in such a forest.
2.
New unvisited vertex is reached for the first time,
the vertex is attached as a child to the vertex it is being reached from with
an edge called a tree edge.
3.
If an edge leading to a previously visited vertex
other than its immediate predecessor (i.e., its parent in the tree) is
encountered, the edge is noted as a
cross edge.
♦ Here is a
pseudo code of the breadth-first search.
ALGORITHM BFS(G)
//Implements a breadth-first search traversal of a
given graph //Input: Graph G = (V, E)
//Output:
Graph G with its vertices marked with consecutive integers in the order they
have been visited by the BFS traversal mark each vertex in V with 0 as a mark of being
"unvisited" count ! 0
for each
vertex v in V do if v is marked with
0 bfs(v)
bfs(v)
//visits
all the unvisited vertices connected to vertex v and assigns them the numbers
in the order they are visited via global variable count
count ! count + 1; mark v with count and
initialize a queue with v while the queue is not empty do
for each
vertex w in V adjacent to the front's vertex
v do if w is marked with 0
count ! count +
1; mark w with count add w to the queue
remove vertex v from the front of the
queue
2. EFFICIENCY
♦
Breadth-first search has the same efficiency as depth-first search:
♦ BFS can be used to check the connectivity and
acyclicity of a graph as same as DFS. for the adjacency linked list
representation.
3. ORDERING OF VERTICES
♦ It yields
a single ordering of vertices because the queue is a FIFO (first-in first-out)
structure, and hence the order in which vertices are added to the queue is the
same order in which they are removed from it.
♦ As to the
structure of a BFS forest, it can also have two kinds of edges: tree edges and
cross edges. Tree edges are the ones used to reach previously unvisited
vertices. Cross edges connect vertices to those visited before but, unlike back
edges in a DFS tree, they connect either siblings or cousins on the same or
adjacent levels of a BFS tree.
4. APPLICATION OF BFS
♦ Finally,
BFS can be used to
♦ Check
connectivity and acydicity of a graph
♦ BFS can
be used for finding a path with the fewest number of edges between two given
vertices.
♦ This figure
explains the BFS algorithm to find the minimum edge path.
5 PROCEDURE TO FIND THE FEWEST NUMBER OF EDGES
BETWEEN TWO VERTICES:
♦ Start a
BFS traversal at one of the given edge
♦ Stop it
as soon as the other vertex is reached.
♦ For
example, path a-b-e-g in the graph has the fewest number of edges among all the
paths between
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.