exp-10.c

#include <stdio.h>

#define QUEUE_SIZE 100
#define STACK_SIZE 100
#define MAX_CONN 8

int queue[QUEUE_SIZE];
int front = -1, rear = -1;

int stack[STACK_SIZE];
int top = -1;
void push(int val) {
    stack[++top] = val;
}

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

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

void enqueue(int val) {
	if (rear == QUEUE_SIZE - 1) {
		return;
	}

	if (front == -1) front = 0;
	queue[++rear] = val;
}

int dequeue() {
	if (front == -1 || front > rear) return -1;

	int val = queue[front];
	front++;
	return val;
}

int isEmpty() {
	return (front == -1 || front > rear);
}

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

	while (!isEmpty()) {
		int a = dequeue();
		printf("%c ", 'A' + a);

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

void dfs(int start) {
	vis[start] = 1;
	printf("%c ", 'A' + start);

	for (int i = 0; i < MAX_CONN; i++) {
		if (graph[start][i] && !vis[i]) {
			dfs(i);
		}
	}
}

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

	for (int i = 0; i < MAX_CONN; i++) {
		if (graph[start][i] && !vis[i]) {
			topoDfs(i);
		}
	}

	push(start);
}

void topoSort() {
	top = -1;

	for (int i = 0; i < MAX_CONN; i++) {
		if (!vis[i]) {
			topoDfs(i);
		}
	}

	while (top != -1) {
		printf("%c ", 'A' + stack[top--]);
	}
}

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

  printf("BFS: ");
  bfs('B' - 'A'); // start form B

  // reset visit details
  for (int i = 0; i < MAX_CONN; i++) vis[i] = 0;

	printf("\nDFS: ");
	dfs('B' - 'A'); // start from B

	// reset visit details
  for (int i = 0; i < MAX_CONN; i++) vis[i] = 0;

  printf("\nTopological order: ");
	topoSort();

  return 0;
}