Graph BFS
Thu Oct 26 2023 17:58:08 GMT+0000 (Coordinated Universal Time)
Saved by @Astik
#include<stdio.h> #include<stdlib.h> #include<conio.h> #define MAX_NODES 20 int visited[MAX_NODES]; int graph[MAX_NODES][MAX_NODES]; int i,j; struct Queue { int front, rear, size; int capacity; int* array; }; struct Queue* createQueue(int capacity) { struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue)); queue->capacity = capacity; queue->front = queue->size = 0; queue->rear = capacity - 1; queue->array = (int*)malloc(queue->capacity * sizeof(int)); return queue; } int isFull(struct Queue* queue) { return (queue->size == queue->capacity); } int isEmpty(struct Queue* queue) { return (queue->size == 0); } void enqueue(struct Queue* queue, int item) { if (isFull(queue)) return; queue->rear = (queue->rear + 1) % queue->capacity; queue->array[queue->rear] = item; queue->size = queue->size + 1; } int dequeue(struct Queue* queue) { int item; if (isEmpty(queue)) return -1; item = queue->array[queue->front]; queue->front = (queue->front + 1) % queue->capacity; queue->size = queue->size - 1; return item; } void bfs(int start_node, int n) { struct Queue* queue = createQueue(n); visited[start_node] = 1; enqueue(queue, start_node); printf("BFS traversal starting from node %d: ", start_node); while (!isEmpty(queue)) { int current_node = dequeue(queue); printf("%d ", current_node); for (i = 0; i < n; i++) { if (graph[current_node][i] && !visited[i]) { visited[i] = 1; enqueue(queue, i); } } } free(queue); } int main() { int n,start_node; printf("Enter the number of nodes (Less than or equal to %d): ", MAX_NODES); scanf("%d", &n); printf("Enter the adjacency matrix (0 or 1):\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { printf("i=%d, j=%d Enter: ",i,j); scanf("%d", &graph[i][j]); } } printf("Enter the starting node for BFS: "); scanf("%d", &start_node); bfs(start_node, n); printf("\n"); getch(); return 0; }
Comments