1. ## DFS in C

Hi, I'm trying to implement DFS for graphs in C using an iterative process using the following algorithm:

Code:
```Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Push the starting node A on the stack and set
its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4:
Pop the top node N. Process it and set its
STATUS = 3 (processed state)
Step 5:
Push on the stack all the neighbours of N that
are in the ready state (whose STATUS = 1) and
set their STATUS = 2 (waiting state)
[END OF LOOP]
Step 6: EXIT```
The code I have developed for this is as follows:
Code:
```#include <stdio.h>
#define SIZE 10

typedef struct
{
int element[SIZE];
int top;
}stack;

void push(stack *s, int item)
{
if(s->top >= (SIZE - 1))
return;
s->element[++(s->top)] = item;
}

int pop(stack *s)
{
if(s->top <= -1)
return -1;

return s->element[(s->top)--];
}

{
int i, j;
printf("Enter elements of %dx%d adjacency matrix\n", n, n);

for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &matrix[i][j]);
}

void dfs(int adj[SIZE][SIZE], int start, int visited[], int n, stack* s)
{
int i;
push(s, start);
visited[start] = 1;

while(s->top != -1)
{
int node = pop(s);
printf("%d\t", node);

// for(i = n; i >= 0; i--)
for(i = 0; i < n; i++)
{
if(adj[node][i] == 1 && visited[i] == 0)
{
push(s, i);
visited[i] = 1;
}
}

}
printf("\n");
}

void main()
{
stack s;
s.top = -1;

printf("Enter no. of vertices\n");
scanf("%d", &n);

printf("Enter starting vertex\n");
scanf("%d", &start);
}```
The iterative approach seems to yield a different result when compared to the recursive approach, even if I change the direction of traversing the array. I did refer a few books which trace the algorithm and this does seem to be correct I guess.
Can anyone see if it's correct or am I missing something?
Thanks 2. Perhaps it would be easier if you provided your implementation of the recursive approach too, as well as your test input data that demonstrates the different result. 3. Originally Posted by laserlight Perhaps it would be easier if you provided your implementation of the recursive approach too, as well as your test input data that demonstrates the different result.
My recursive approach is as follows:

Code:
```DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)```
Code:
```void dfs1(int i, int visited[], int adj[SIZE][SIZE], int n)
{
printf("%d", i);
visited[i] = 1;
for(int j = 0; j < n; j++)
{
}
}```
Code:
```0 1 1 1 0 0 0
1 0 1 0 0 0 0
1 1 0 1 1 0 0
1 0 1 0 1 0 0
0 0 1 1 0 1 1
0 0 0 0 1 0 0
0 0 0 0 1 0 0```
Starting vertex as 1 yields different results.

I realise why it yields different results and also the fact that the way you traverse the adjacency matrix also matters so different valid traversals are possible.
In the recursive approach, only one unvisited neighbour of a vertex is pushed onto the stack at a time but in the iterative version all unvisited neighbours are pushed onto the stack. It's just that the recursive version seems to be the most popular version in most online guides and I'm unsure as to if my approach gives another valid traversal or is just incorrect in some way. Popular pages Recent additions dfs, int, state, status, step 