1// Aim: Program to perform Depth First Search (DFS) on a graph.
2#include <stdio.h>
3#include <stdlib.h>
4
5#define MAX 20
6int s[MAX], t = -1, nv, am[MAX][MAX], visited[MAX];
7void push(int item) {
8    if (t==MAX)
9    {
10        printf("stack overflow\n");
11        return;
12    }
13    
14    else 
15    {
16        t++;  
17    }
18    s[t] = item;
19}
20
21int pop() {
22    if (t== -1)
23    {
24        printf("stack is empty\n");
25        return -1;  
26    }
27    int item = s[t];
28    t--;
29    return item;
30}
31
32void bfs(int sv){
33    visited[sv] = 1;
34    push(sv);
35
36    printf("DFS Traversal: ");
37
38    while (t != -1) 
39    {
40        int cv = pop();
41        printf("v%d ", cv);
42
43        for (int i = 0; i < nv; i++)
44        {
45            if (am[cv][i] == 1 && visited[i] == 0)
46            {
47                visited[i] = 1;
48               push(i);
49            }
50        }
51    }
52    printf("\n");
53}
54
55int main(){
56    int e, sv;
57
58    printf("Enter the number of vertices: ");
59    scanf("%d", &nv);
60    for (int i = 0; i < nv; i++)
61    {
62        visited[i] = 0;
63        for (int j = 0; j < nv; j++)
64        {
65            am[i][j] = 0;
66        }
67    }
68
69    for (int i = 0; i < nv; i++) 
70    {
71        for (int j = 0; j < nv; j++)
72        {
73            if (i != j) { 
74                printf("Do you want to create an edge between v%d and v%d? (enter 1 for yes, 0 for no): ", i, j);
75                scanf("%d", &e);
76                if (e == 1) 
77                {
78                    am[i][j] = 1;  
79                }
80            }
81        }
82    }
83
84    printf("Adjacency matrix:\n");
85    for (int i = 0; i < nv; i++) 
86    {
87        for (int j = 0; j < nv; j++) 
88        {
89            printf("%d ", am[i][j]);
90        }
91        printf("\n");
92    }
93
94    printf("Enter the starting vertex (0 to %d): ", nv - 1);
95    scanf("%d", &sv);
96
97    bfs(sv);
98
99    return 0;
100}