bfs.c
graphs Implementation
74 lines1410 bytesC
1// Graph - BFS (Breadth First Search)
2#include <stdio.h>
3#include <stdlib.h>
4#define MAX 100
5
6struct Queue {
7 int items[MAX];
8 int front, rear;
9};
10
11void initQueue(struct Queue* q) {
12 q->front = -1;
13 q->rear = -1;
14}
15
16int isEmpty(struct Queue* q) {
17 return q->front == -1;
18}
19
20void enqueue(struct Queue* q, int value) {
21 if (q->rear == MAX - 1) return;
22 if (q->front == -1) q->front = 0;
23 q->rear++;
24 q->items[q->rear] = value;
25}
26
27int dequeue(struct Queue* q) {
28 int item = q->items[q->front];
29 q->front++;
30 if (q->front > q->rear) {
31 q->front = q->rear = -1;
32 }
33 return item;
34}
35
36void BFS(int graph[][MAX], int vertices, int start) {
37 int visited[MAX] = {0};
38 struct Queue q;
39 initQueue(&q);
40
41 visited[start] = 1;
42 enqueue(&q, start);
43
44 printf("BFS Traversal: ");
45
46 while (!isEmpty(&q)) {
47 int current = dequeue(&q);
48 printf("%d ", current);
49
50 for (int i = 0; i < vertices; i++) {
51 if (graph[current][i] == 1 && !visited[i]) {
52 visited[i] = 1;
53 enqueue(&q, i);
54 }
55 }
56 }
57 printf("\n");
58}
59
60int main() {
61 int vertices = 5;
62 int graph[MAX][MAX] = {
63 {0, 1, 1, 0, 0},
64 {1, 0, 0, 1, 1},
65 {1, 0, 0, 0, 1},
66 {0, 1, 0, 0, 0},
67 {0, 1, 1, 0, 0}
68 };
69
70 BFS(graph, vertices, 0);
71
72 return 0;
73}
74