C program for Breadth First Search.

Posted by Mangesh on September 03, 2019

Breadth-First Search

Breadth-first search (BFS) is a general technique for traversing a graph
A BFS traversal of a graph G
Visits all the vertices and edges of G
Determines whether G is connected
Computes the connected components of G
Computes a spanning forest of G

BFS on a graph with n vertices and m edges takes O(n + m ) time
BFS can be further extended to solve other graph problems
Find and report a path with the minimum number of edges between two given vertices

Analysis

Setting/getting a vertex/edge label takes O(1) time q Each vertex is labeled twice
once as UNEXPLORED
once as VISITED
Each edge is labeled twice
once as UNEXPLORED
once as DISCOVERY or CROSS
Each vertex is inserted once into a sequence Li
Method incidentEdges is called once for each vertex
BFS runs in O(n + m) time provided the graph is represented by the adjacency list structure

Notation Gs: connected component of s

Property 1 BFS (G, s) visits all the vertices and edges of Gs
Property 2 The discovery edges labeled by BFS (G, s) form a spanning tree Ts of Gs
Property 3 For each vertex v in Li n The path of Ts from s to v has i edges n Every path from s to v in Gs has at least i edges

Applications

q We can specialize the BFS traversal of a graph G to solve the following problems in O(n + m) time
n Compute the connected components of G
n Compute a spanning forest of G
n Given two vertices of G, find a path in G between them with the minimum number of edges, or report that no such path exists
n Check if a connected graph G is bipartite.

Written with from Mangesh.

Related Post
1 C program for Depth First Search(DFS).
2 C program for Breadth First Search.
Latest Post
1 shubhanshu
2 test
3 C program for Breadth First Search.
4 C program for Depth First Search(DFS).
5 C for circular queue using linked list.