calgorithmdata-structuresgraph-theorydepth-first-search

# Different output from dfs iterative and dfs recursive

This program is for dfs traversal of graph one function is a iterative method and another function is a recursive method but both are giving different answer from iterative i am getting `01234` from recursive i am getting `02341` can any one explain me why?

NOTE -> User is entering weights here but they are of no use in this implementation of dfs ,i was implementing dijkstra so i considered the weights there ,iam telling you this so that you will not confuse

program is exactly correct you can paste it in your compiler

``````// C program for array implementation of stack
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// A structure to represent a stack
struct Stack
{
int top;
unsigned capacity;
int* array;
};
int visited[100];
// function to create a stack of given capacity. It initializes size of
// stack as 0
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}

// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
return stack->top == stack->capacity - 1;
}

// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}

// Function to add an item to stack. It increases top by 1
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
//printf("%d pushed to stack\n", item);
}

// Function to remove an item from stack. It decreases top by 1
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}

int data;
};
};
struct graph {
int v;
};
struct graph* creategraph(int v) {
struct graph* G = (struct graph*) malloc(sizeof(struct graph));
G->v = v;
int i;
for (i = 0; i < v; i++) {
}
return G;
}
int weight[100][100], Distance[50], path[50];
newnode->data = ver;
newnode->next = NULL;
return newnode;

}
void addedge(struct graph* G, int src, int dest) {
temp = getnewnode(dest);

//temp = getnewnode(src);
printf("  Enter the weight :  ");
int w;
scanf("%d", &w);
weight[src][dest] = w;
weight[dest][src] = w;
}
void printgraph(struct graph* G) {
for (int i = 0; i < G->v; i++) {
printf("%d->   ", i);
while (temp) {
printf(" %d", temp->data);
temp = temp->next;
}
printf("\n");
}
}

// Driver program to test above functions
void dfsiterative(struct graph* G, struct Stack* stack, int s) {
int v, w;
push(stack, s);
visited[s] = 1;
while (!isEmpty(stack)) {
v = pop(stack);

printf("%d", v); ///process v
while (temp) {
w = temp->data;
if (visited[w] == 0) {
push(stack, w);
visited[w] = 1;
}
temp = temp->next;
}
}
}
void dfsrecursive(struct graph* G, int s) {
visited[s] = 1;
printf("%d", s);
while (temp) {
int w = temp->data;
if (visited[w] == 0) {
dfsrecursive(G, w);
temp = temp->next;
}
}
}

int main()
{
// Create a Priority Queue
// 7->4->5->6
struct Stack* stack = createStack(100);
struct graph* G = creategraph(5);
for (int i = 0; i < 30; i++) {
visited[i] = 0;
}
printgraph(G);
printf("\n");

//dfsiterative(G,stack,0);
dfsrecursive(G, 0);

return 0;
}
``````

Solution

• Your iterative and recursive dfs functions produce different outputs because they operate differently when a node is connected to multiple nodes.

To take your example, `0` is connected to `1` and `2`.

The recursive function will call `dfsrecursive` on `1` as it's the first node in adjacency list and thus `1` will appear before `2`.

In the iterative version, both `1` and `2` will be pushed on the stack in order. Since `2` was pushed last, it will be popped before `1`. Hence, `2` will be printed before `1`.

Obviously, this change in order also affects other nodes as the two algorithms diverge.

I don't really see any problem with this, but if it bothers you, you can try reversing the order in which you push adjacent nodes to the stack. That should fix this problem.