Question

In C language. Write a Code for Implementation of Depth-First Traversal and Breath-First Traversal on a given graph havin (8 vertices and 12 sides)

Answer 1

#include <stdio.h>

void dfs_exec(int adj[8][8], int visited[8], int v) {
printf("%d ", v);
visited[v] = 1;
int i;
for (i = 0; i < 8; i++)
& if (adj[v][i] == 1 && visited[i] == 0)
dfs_exec(adj, visited, i);
}

void dfs(int adj[8][8]) {
printf("Depth-First Traversal:\n");
int visited[8] = {};
int i;
for (i = 0; i < 8; i++)
& if (visited[i] == 0) {
dfs_exec(adj, visited, i);
printf("\n");
& }
}

void bfs(int adj[8][8]) {
printf("Breath-First Traversal:\n");
int Q[8];
int visited[8] = {};
int k;
for (k = 0; k < 8; k++)
& if (visited[k] == 0) {
& int head = 0, tail = 0;
& Q[0] = k;
& visited[0] = 1;
& while (head <= tail) {
int v = Q[head];
printf("%d ", v);
int i;
for (i = 0; i < 8; i++)
if (adj[v][i] == 1 && visited[i] == 0) {
& Q[++tail] = i;
& visited[i] = 1;
}
++head;
& }
& printf("\n");
& }
}

int main() {
int i;
int adj[8][8] = {};
for (i = 0; i < 12; i++) {
& printf("Input edge %d vertices: ", i);
& int a, b;
& scanf("%d %d", &a, &b);
& adj[a][b] = 1;
& adj[b][a] = 1;
}
dfs(adj);
bfs(adj);
}