Question #27439

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)

Expert's answer

#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);

}

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);

}

## Comments

## Leave a comment