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)--];
}
void inputadjmat(int matrix[SIZE][SIZE], int n)
{
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;
int adj[SIZE][SIZE], visited[SIZE], n, start;
s.top = -1;
printf("Enter no. of vertices\n");
scanf("%d", &n);
inputadjmat(adj, n);
printf("Enter starting vertex\n");
scanf("%d", &start);
dfs(adj, start, visited, n, &s);
}
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