Graph Traversals - Breadth First Search Working Principle

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