KEMBAR78
BFS DFS Graph Programs | PDF | Algorithms And Data Structures | Combinatorics
Scribd
Upload
19 views5 pages

BFS DFS Graph Programs

The document provides C programs for graph traversal using both adjacency matrix and adjacency list representations. It includes implementations for Breadth-First Search (BFS) and Depth-First Search (DFS) for both representations, demonstrating how to traverse a graph starting from a specified node. Each section includes code snippets and explanations for setting up the graph and executing the traversal algorithms.

Uploaded by

satya.alugolu6511
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
19 views5 pages

BFS DFS Graph Programs

The document provides C programs for graph traversal using both adjacency matrix and adjacency list representations. It includes implementations for Breadth-First Search (BFS) and Depth-First Search (DFS) for both representations, demonstrating how to traverse a graph starting from a specified node. Each section includes code snippets and explanations for setting up the graph and executing the traversal algorithms.

Uploaded by

satya.alugolu6511
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Graph Traversal Programs in C

1. BFS and DFS using Adjacency Matrix

1.1 Breadth-First Traversal (BFS)

#include <stdio.h>
#define SIZE 10

int adj[SIZE][SIZE], visited[SIZE], queue[SIZE];


int front = -1, rear = -1;

void bfs(int start, int n) {


visited[start] = 1;
queue[++rear] = start;

while (front != rear) {


int curr = queue[++front];
printf("%d ", curr);

for (int i = 0; i < n; i++) {


if (adj[curr][i] && !visited[i]) {
queue[++rear] = i;
visited[i] = 1;
}
}
}
}

int main() {
int n = 4;
int temp[4][4] = {
{0,1,1,0},
{1,0,1,1},
{1,1,0,0},
{0,1,0,0}
};

for (int i = 0; i < n; i++)


for (int j = 0; j < n; j++)
adj[i][j] = temp[i][j];
printf("BFS starting from node 0:\n");
bfs(0, n);
return 0;
}

1.2 Depth-First Traversal (DFS)

#include <stdio.h>
#define SIZE 10

int adj[SIZE][SIZE], visited[SIZE];

void dfs(int v, int n) {


visited[v] = 1;
printf("%d ", v);

for (int i = 0; i < n; i++) {


if (adj[v][i] && !visited[i]) {
dfs(i, n);
}
}
}

int main() {
int n = 4;
int temp[4][4] = {
{0,1,1,0},
{1,0,1,1},
{1,1,0,0},
{0,1,0,0}
};

for (int i = 0; i < n; i++)


for (int j = 0; j < n; j++)
adj[i][j] = temp[i][j];

printf("DFS starting from node 0:\n");


dfs(0, n);
return 0;
}
2. BFS and DFS using Adjacency List

2.1 Breadth-First Traversal (BFS)

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

#define SIZE 10

typedef struct Node {


int data;
struct Node* next;
} Node;

Node* adj[SIZE];
int visited[SIZE], queue[SIZE];
int front = -1, rear = -1;

void addEdge(int u, int v) {


Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = v;
newNode->next = adj[u];
adj[u] = newNode;
}

void bfs(int start) {


visited[start] = 1;
queue[++rear] = start;

while (front != rear) {


int curr = queue[++front];
printf("%d ", curr);

Node* temp = adj[curr];


while (temp) {
if (!visited[temp->data]) {
queue[++rear] = temp->data;
visited[temp->data] = 1;
}
temp = temp->next;
}
}
}
int main() {
int n = 4;
addEdge(0,1); addEdge(0,2);
addEdge(1,0); addEdge(1,2); addEdge(1,3);
addEdge(2,0); addEdge(2,1);
addEdge(3,1);

printf("BFS starting from node 0:\n");


bfs(0);
return 0;
}

2.2 Depth-First Traversal (DFS)

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

#define SIZE 10

typedef struct Node {


int data;
struct Node* next;
} Node;

Node* adj[SIZE];
int visited[SIZE];

void addEdge(int u, int v) {


Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = v;
newNode->next = adj[u];
adj[u] = newNode;
}

void dfs(int v) {
visited[v] = 1;
printf("%d ", v);

Node* temp = adj[v];


while (temp) {
if (!visited[temp->data]) {
dfs(temp->data);
}
temp = temp->next;
}
}

int main() {
int n = 4;
addEdge(0,1); addEdge(0,2);
addEdge(1,0); addEdge(1,2); addEdge(1,3);
addEdge(2,0); addEdge(2,1);
addEdge(3,1);

printf("DFS starting from node 0:\n");


dfs(0);
return 0;
}

You might also like