bfs.c

graphs Implementation

74 lines
1410 bytes
C
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