bfs.c

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

typedef struct Node {
	int data;
	struct Node *next;
} Node;

typedef struct Queue {
	Node *start, *end;
} Queue;

int graph[MAX][MAX];
int vis[MAX] = {0};

Queue q = {NULL, NULL};

void addEdge(int a, int b) {
	graph[a][b] = 1;
}

void enqueue(int data) {
	Node *n = (Node*)calloc(1, sizeof(Node));
	n->data = data;

	if (!q.start) {
		q.start = q.end = n;
	} else {
		q.end->next = n;
		q.end = n;
	}
}

int dequeue() {
	if (!q.start) return -1;

	Node *temp = q.start;
	int d = temp->data;

	q.start = q.start->next;

	if (!q.start) q.end = NULL;

	free(temp);
	return d;
}

void bfs(int start) {
	enqueue(start);
	vis[start] = 1;

	while (q.start) {
		int a = dequeue();
		printf("%c ", 'A' + a);

		for (int i = 0; i < MAX; i++) {
			if (graph[a][i] && !vis[i]) {
				enqueue(i);
				vis[i] = 1;
			}
		}
	}
}

int main() {
	addEdge(0,1); // A→B
  addEdge(0,3); // A→D
  addEdge(0,2); // A→C

  addEdge(1,4); // B→E
  addEdge(1,2); // B→C

  addEdge(2,4); // C→E

  addEdge(3,2); // D→C
  addEdge(3,5); // D→F

  addEdge(4,0); // E→A

  addEdge(5,2); // F→C

  addEdge(6,3); // G→D
  addEdge(6,5); // G→F
  addEdge(6,7); // G→H

  addEdge(7,2); // H→C

  bfs('A' - 'B'); // start from B
	
	return 0;
}