dfs 迭代和 dfs 递归的不同输出

Question

此程序用于图的dfs遍历，一个函数是迭代法，另一个函数是递归法，但两者给出的答案不同从迭代中我得到 01234 从递归我得到 02341 谁能解释我为什么？

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

程序完全正确，您可以将其粘贴到您的编译器中

// 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

您的迭代和递归 dfs 函数产生不同的输出，因为当一个节点连接到多个节点时它们的操作不同。

举个例子，0 连接到 1 和 2。

递归函数将在 1 上调用 dfsrecursive，因为它是邻接列表中的第一个节点，因此 1 将出现在 2 之前。

在迭代版本中，1和2都会按顺序入栈。由于 2 最后被压入，它将在 1 之前被弹出。因此，2 将在 1.

之前打印

显然，由于两种算法不同，这种顺序变化也会影响其他节点。

我真的看不出这有什么问题，但如果它困扰您，您可以尝试颠倒将相邻节点推入堆栈的顺序。这应该可以解决这个问题。

dfs 迭代和 dfs 递归的不同输出

Different output from dfs iterative and dfs recursive

c

algorithm

graph-theory

depth-first-search

data-structures