bfs c

1// BFS algorithm in C
2
3#include <stdio.h>
4#include <stdlib.h>
5#define SIZE 40
6
7struct queue {
8  int items[SIZE];
9  int front;
10  int rear;
11};
12
13struct queue* createQueue();
14void enqueue(struct queue* q, int);
15int dequeue(struct queue* q);
16void display(struct queue* q);
17int isEmpty(struct queue* q);
18void printQueue(struct queue* q);
19
20struct node {
21  int vertex;
22  struct node* next;
23};
24
25struct node* createNode(int);
26
27struct Graph {
28  int numVertices;
29  struct node** adjLists;
30  int* visited;
31};
32
33// BFS algorithm
34void bfs(struct Graph* graph, int startVertex) {
35  struct queue* q = createQueue();
36
37  graph->visited[startVertex] = 1;
38  enqueue(q, startVertex);
39
40  while (!isEmpty(q)) {
41    printQueue(q);
42    int currentVertex = dequeue(q);
43    printf("Visited %d\n", currentVertex);
44
45    struct node* temp = graph->adjLists[currentVertex];
46
47    while (temp) {
48      int adjVertex = temp->vertex;
49
50      if (graph->visited[adjVertex] == 0) {
51        graph->visited[adjVertex] = 1;
52        enqueue(q, adjVertex);
53      }
54      temp = temp->next;
55    }
56  }
57}
58
59// Creating a node
60struct node* createNode(int v) {
61  struct node* newNode = malloc(sizeof(struct node));
62  newNode->vertex = v;
63  newNode->next = NULL;
64  return newNode;
65}
66
67// Creating a graph
68struct Graph* createGraph(int vertices) {
69  struct Graph* graph = malloc(sizeof(struct Graph));
70  graph->numVertices = vertices;
71
72  graph->adjLists = malloc(vertices * sizeof(struct node*));
73  graph->visited = malloc(vertices * sizeof(int));
74
75  int i;
76  for (i = 0; i < vertices; i++) {
77    graph->adjLists[i] = NULL;
78    graph->visited[i] = 0;
79  }
80
81  return graph;
82}
83
84// Add edge
85void addEdge(struct Graph* graph, int src, int dest) {
86  // Add edge from src to dest
87  struct node* newNode = createNode(dest);
88  newNode->next = graph->adjLists[src];
89  graph->adjLists[src] = newNode;
90
91  // Add edge from dest to src
92  newNode = createNode(src);
93  newNode->next = graph->adjLists[dest];
94  graph->adjLists[dest] = newNode;
95}
96
97// Create a queue
98struct queue* createQueue() {
99  struct queue* q = malloc(sizeof(struct queue));
100  q->front = -1;
101  q->rear = -1;
102  return q;
103}
104
105// Check if the queue is empty
106int isEmpty(struct queue* q) {
107  if (q->rear == -1)
108    return 1;
109  else
110    return 0;
111}
112
113// Adding elements into queue
114void enqueue(struct queue* q, int value) {
115  if (q->rear == SIZE - 1)
116    printf("\nQueue is Full!!");
117  else {
118    if (q->front == -1)
119      q->front = 0;
120    q->rear++;
121    q->items[q->rear] = value;
122  }
123}
124
125// Removing elements from queue
126int dequeue(struct queue* q) {
127  int item;
128  if (isEmpty(q)) {
129    printf("Queue is empty");
130    item = -1;
131  } else {
132    item = q->items[q->front];
133    q->front++;
134    if (q->front > q->rear) {
135      printf("Resetting queue ");
136      q->front = q->rear = -1;
137    }
138  }
139  return item;
140}
141
142// Print the queue
143void printQueue(struct queue* q) {
144  int i = q->front;
145
146  if (isEmpty(q)) {
147    printf("Queue is empty");
148  } else {
149    printf("\nQueue contains \n");
150    for (i = q->front; i < q->rear + 1; i++) {
151      printf("%d ", q->items[i]);
152    }
153  }
154}
155
156int main() {
157  struct Graph* graph = createGraph(6);
158  addEdge(graph, 0, 1);
159  addEdge(graph, 0, 2);
160  addEdge(graph, 1, 2);
161  addEdge(graph, 1, 4);
162  addEdge(graph, 1, 3);
163  addEdge(graph, 2, 4);
164  addEdge(graph, 3, 4);
165
166  bfs(graph, 0);
167
168  return 0;
169}

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