In this tutorial we will discuss about Breadth First Search or BFS program in C with algorithm and an example. Before jumping to actual coding lets discuss something about Graph and BFS.

**Also Read: Depth First Search (DFS) Traversal of a Graph [Algorithm and Program]**

A Graph G = (V, E) is a collection of sets V and E where V is a collection of vertices and E is a collection of edges.

A Graph can be of two types:

1. Directed Graph

2. Undirected Graph

In data structures, there is a popular term known as ‘Traversal’. It is the process of systematically visiting or examining (may be to update the Graph nodes) each node in a tree data structure, exactly once.

There are two most common methods to traverse a Graph:

1. Breadth First Search

2. Depth First Search

In this tutorial, we are going to focus on Breadth First Search technique.

In this technique, we first visit the vertex and then visit all the vertices adjacent to the starting vertex i.e., 0. Next, we pick the adjacent vertices one after another and visit their adjacent vertices and this process goes on and on until we reach the last vertex.

## Breadth First Search (BFS) Example

Consider below Graph as an example.

The vertex 0 is the starting vertex in our case. We start our traversal from the vertex 0. Then we will visit all vertices adjacent to vertex 0 i.e., 1, 4, 3. Here, we can visit these three vertices in any order. Suppose we visit the vertices in order 1,3,4.

The traversal would be: 0 1 3 4

Now, we shall visit all the vertices adjacent to 1, then all the vertices adjacent to 3 and then all the vertices adjacent to 4. So first we shall visit 2 (since it is adjacent to 1), then 6 (since it is adjacent to 3) and 5, 7 (since these are adjacent to 4).

**Note:** Vertex 4 is adjacent to vertices 1 and 3, but it has already been visited so we’ve ignored it.

The traversal would be: 0 1 3 4 2 6 5 7

Now, we shall visit all the vertices adjacent to 2, 6, 5, and 7 one by one. We can see that vertex 5 is adjacent to vertex 2. Since, it has already been traversed upon before, we have don’t need to traverse through it again and move on to the next vertex. Now, the vertices 4 and 7 are adjacent to the vertex 6. Since, they have been traversed upon before, we will not traverse on them again. Vertex 5 does not have any adjacent vertices. Vertices 5 and 8 are adjacent to vertex 7. Since, vertex 5 has been traversed upon before, we will not traverse it again. However, vertex 8 has not yet been visited. So we will traverse on vertex 8.

The traversal would be: 0 1 3 4 2 6 5 7 8

Now, we need to visit vertices adjacent to vertex 8. However, there is no vertex adjacent to vertex 8 and hence we will have to stop the traversal here.

**Note:** There’s no unique traversal and it can be different based on the order of the successors.

We shall look at a BFS program in C for directed Graph using a Queue. This program reaches only those vertices that are reachable from the start vertex.

## Breadth First Search (BFS) Program in C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 int n; int adj[MAX][MAX]; int state[MAX]; void create_graph(); void BF_Traversal(); void BFS(int v); int queue[MAX], front = -1,rear = -1; void insert_queue(int vertex); int delete_queue(); int isEmpty_queue(); int main() { create_graph(); BF_Traversal(); return 0; } void BF_Traversal() { int v; for(v=0; v<n; v++) state[v] = initial; printf("Enter Start Vertex for BFS: \n"); scanf("%d", &v); BFS(v); } void BFS(int v) { int i; insert_queue(v); state[v] = waiting; while(!isEmpty_queue()) { v = delete_queue( ); printf("%d ",v); state[v] = visited; for(i=0; i<n; i++) { if(adj[v][i] == 1 && state[i] == initial) { insert_queue(i); state[i] = waiting; } } } printf("\n"); } void insert_queue(int vertex) { if(rear == MAX-1) printf("Queue Overflow\n"); else { if(front == -1) front = 0; rear = rear+1; queue[rear] = vertex ; } } int isEmpty_queue() { if(front == -1 || front > rear) return 1; else return 0; } int delete_queue() { int delete_item; if(front == -1 || front > rear) { printf("Queue Underflow\n"); exit(1); } delete_item = queue[front]; front = front+1; return delete_item; } void create_graph() { int count,max_edge,origin,destin; printf("Enter number of vertices : "); scanf("%d",&n); max_edge = n*(n-1); for(count=1; count<=max_edge; count++) { printf("Enter edge %d( -1 -1 to quit ) : ",count); scanf("%d %d",&origin,&destin); if((origin == -1) && (destin == -1)) break; if(origin>=n || destin>=n || origin<0 || destin<0) { printf("Invalid edge!\n"); count--; } else { adj[origin][destin] = 1; } } } |

**Output**

If you find anything incorrect or have any doubts regarding above Breadth First Search (BFS) program in C then comment below.

Akhilesh Kumarthis code may not work in case of disjoint graphs

add

for(i=1;i<=n;i++)

if(state[i]==initial;)

bfs(i,n);

Kaustubhthis code is for bfs. what you are saying is the code for bf traversal. both are different.

Shithi MaitraThis was of great help. But I have two questions.

1. In the input, you have excluded two connections : 1 4 and 3 4 ; while I ran this code including these edged, it rendered the same output. What is actually happening here?

2. Do you have a Dijkstra code written in the same fashion? If so, plz provide me.

All the best. 🙂

Indrajit SinhaCan I use this program for undirected graph also

xenderno

Shriyanshis it possible to use bfs and dfs on undirected graphs?

sujanHow to use it for undirected graphs?

sandeshcan i input edges as character ex: like a,b .any changes to make in this program?

srinadhwhy do we need Waiting state? Isnt Initial and Visited are enough? We dont seem to check for Waiting state anywhere.

mahendranNeeraj mishra jii the way in which you program astonishes me, you are very much talented

Albert EinsteinThanks for the stuff…

very good code..

loved it…

…

Mayur GudiAccording to me correct answer should be

0 1 2 5 4 6 3 7 8

Check it out …

rahul punjabiNo

Kiran Poojaryyes your answer also correct,our goal is to visit every node of the graph.

SumanThanks for the simply illustrated BFS program.

I am new to data structures. I am beginner and have little knowledge on Linked Lists, Circular LLs, Double LLs.

I was in the assumption to create a node with many childs say(similar to Linked List)

struct GraphNode

{

int data;

struct GraphNode *p1;

struct GraphNode *p2;

struct GraphNode *p3;

};

And I am trying to add Nodes one by one to create a graph, and then traverse through all the nodes of the graph(in BFS way).

Anyways Thanks again for simple program.

shruti kuppathil sivaramanexplain me the full code

HarpreetKindly explain d output

JohnWhat would the code look like for c++ ?

praveenthen use it for joint graphs

priyabarata SenHello actually i am a beginner , i am in my second year and i am facing problem to create bfs using linklist . I try to write the code in linklist but don’t know why it’s not working plz help.

#include

#include

typedef struct node

{

struct node *next;

int vertex;

}node;

struct node *front=NULL,*rear=NULL,*q;

node *G[20];

//heads of linked list

int visited[20];

int n;

void read_graph();

//create adjacency list

void insert(int,int);

//insert an edge (vi,vj) in te adjacency list

void BFS(int);

void main()

{

int i;

read_graph();

//initialised visited to 0

for(i=0;ivertex=startvertex;

q->next=NULL;

if(front==NULL & rear== NULL)

front=rear=q;

else

{

rear->next=q;

rear=q;

}

}

int dequeue()

{

struct node *temp;

int data;

if(front==NULL && rear==NULL)

{

printf(“LIST IS EMPTY”);

}

else if(front==rear)

{

data=front->vertex;

return data;

front=rear=NULL;

}

else

{

temp=front;

data=front->vertex;

front=front->next;

free(temp);

}

}

int isempty()

{

if(rear==NULL)

return 1;

else

return 0;

}

void BFS (int startvertex)

{

visited[startvertex]=1;

enqueue(startvertex);

while(!isempty())

{

int current = dequeue();

printf(“Visited %d\n”,current);

struct node *temp=G[current];

while(temp)

{

int adjvertex=temp->vertex;

if(visited[adjvertex]==0)

{

visited[adjvertex]=1;

enqueue(adjvertex);

}

temp=temp->next;

}

}

}

void read_graph()

{

int i,vi,vj,no_of_edges;

printf(“Enter number of vertices:”);

scanf(“%d”,&n);

//initialise G[] with a null

for(i=0;i<n;i++)

{

G[i]=NULL;

//read edges and insert them in G[]

printf("Enter number of edges:");

scanf("%d",&no_of_edges);

for(i=0;ivertex=vj;

q->next=NULL;

//insert the node in the linked list number vi

if(G[vi]==NULL)

G[vi]=q;

else

{

//go to end of the linked list

p=G[vi];

while(p->next!=NULL)

p=p->next;

p->next=q;

}

}