Exp.
10
Implement Graph Traversal techniques : a) Depth First Search
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int adj[MAX][MAX]; // Adjacency matrix
int visited[MAX]; // Visited array
int n; // Number of vertices
// Depth First Search function
void DFS(int v) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < n; i++) {
if (adj[v][i] == 1 && !visited[i]) {
DFS(i);
}
}
}
// Main program
int main() {
int edges, i, origin, destination, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &edges);
// Initialize adjacency matrix
for (i = 0; i < n; i++)
for (int j = 0; j < n; j++)
adj[i][j] = 0;
// Read edges
for (i = 0; i < edges; i++) {
printf("Enter edge %d (from to): ", i + 1);
scanf("%d %d", &origin, &destination);
adj[origin][destination] = 1;
adj[destination][origin] = 1; // For undirected graph
}
// Initialize visited array
for (i = 0; i < n; i++)
visited[i] = 0;
printf("Enter starting vertex for DFS: ");
scanf("%d", &start);
printf("DFS Traversal: ");
DFS(start);
printf("\n");
return 0;
}
Output
Enter number of vertices: 5
Enter number of edges: 4
Enter edge 1 (from to): 0 1
Enter edge 2 (from to): 0 2
Enter edge 3 (from to): 1 3
Enter edge 4 (from to): 2 4
Enter starting vertex for DFS: 0
DFS Traversal: 0 1 3 2 4
b) Breadth first search
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int adj[MAX][MAX]; // Adjacency matrix
int visited[MAX]; // Visited array
int queue[MAX]; // Queue array
int front = -1, rear = -1;
int n; // Number of vertices
// Enqueue operation
void enqueue(int vertex) {
if (rear == MAX - 1)
printf("Queue Overflow\n");
else {
if (front == -1)
front = 0;
rear++;
queue[rear] = vertex;
}
}
// Dequeue operation
int dequeue() {
int vertex;
if (front == -1 || front > rear) {
return -1;
} else {
vertex = queue[front];
front++;
return vertex;
}
}
// BFS function
void BFS(int start) {
int i;
enqueue(start);
visited[start] = 1;
while (front <= rear) {
int current = dequeue();
printf("%d ", current);
for (i = 0; i < n; i++) {
if (adj[current][i] == 1 && !visited[i]) {
enqueue(i);
visited[i] = 1;
}
}
}
}
// Main function
int main() {
int edges, i, origin, destination, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &edges);
// Initialize matrices
for (i = 0; i < n; i++) {
visited[i] = 0;
for (int j = 0; j < n; j++)
adj[i][j] = 0;
}
// Input edges
for (i = 0; i < edges; i++) {
printf("Enter edge %d (from to): ", i + 1);
scanf("%d %d", &origin, &destination);
adj[origin][destination] = 1;
adj[destination][origin] = 1; // For undirected
graph
}
printf("Enter starting vertex for BFS: ");
scanf("%d", &start);
printf("BFS Traversal: ");
BFS(start);
printf("\n");
return 0;
}
Output
Enter number of vertices: 5
Enter number of edges: 4
Enter edge 1 (from to): 0 1
Enter edge 2 (from to): 0 2
Enter edge 3 (from to): 1 3
Enter edge 4 (from to): 2 4
Enter starting vertex for BFS: 0
BFS Traversal: 0 1 2 3 4