Different output from dfs iterative and dfs recursive

Question

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--];
    }



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

    }
    void addedge(struct graph* G, int src, int dest) {
        struct adjlistnode* temp;
        temp = getnewnode(dest);
        temp->next = G->array[src].head;
        G->array[src].head = temp;

        //temp = getnewnode(src);
        ///*temp->next = G->array[dest].head;
        //G->array[dest].head = temp;*/
        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++) {
            struct adjlistnode* temp = G->array[i].head;
            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
            struct adjlistnode* temp = G->array[v].head;
            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);
        struct adjlistnode* temp = G->array[s].head;
        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);
        addedge(G, 0, 1);
        addedge(G, 1, 2);
        addedge(G, 2, 3);
        addedge(G, 3, 4);
        addedge(G, 0, 2);
        for (int i = 0; i < 30; i++) {
            visited[i] = 0;
        }
        printgraph(G);
        printf("\n");

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

        return 0;
    }

Answer 1

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.