2. Write a program to implement Depth First Search traversal of a graph.
// Algorithm: Depth First Search (DFS) Traversal
// Input: G = (V, E): Graph with vertices V and edges E, start ∈ V: Starting vertex,
visited[V]: Boolean array to track visited vertices, adj[V][V]: Adjacency matrix
representation
// Output: Prints DFS traversal order
Step 1: Initialize visited array with all FALSE
Step 2: Read adjacency matrix adj[V][V]
Step 3: Read starting vertex start
Step 4: Print current vertex v
Step 5: Set visited[v] ← TRUE
Step 6: For each vertex u adjacent to v (where adj[v][u] == 1):

If visited[u] == FALSE:
Recursively call DFS(u)

Step 7: Return when all adjacent vertices are processed
#include< stdio.h>
#include< stdlib.h>
#define MAX 100
int adj[MAX][MAX], visited[MAX], n;
void DFS(int vertex)
{
int i;
printf("%d ", vertex);
visited[vertex] = 1;
for(i = 0; i < n; i++)
if(adj[vertex][i] == 1 && !visited[i]) DFS(i);
}
int main()
{
int start, i, j;
printf("Enter number of vertices: "); scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d", &adj[i][j]);
}
visited[i] = 0;
}
printf("Enter starting vertex: "); scanf("%d", &start);
printf("DFS traversal: "); DFS(start);
}