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

Question

这个程序用于图的 dfs 遍历，一个函数是迭代方法，另一个函数是递归方法，但这两个函数都给出了与迭代不同的答案，我01234 从递归中得到了我得到的答案02341，有人可以解释一下为什么吗？

注意 -> 用户在这里输入权重，但它们在 dfs 的实现中没有用处，我正在实现 dijkstra 所以我考虑了那里的权重，我告诉你这一点，这样你就不会混淆

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

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

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

在迭代版本中， 和1都会2按顺序压入堆栈。由于2是最后推送的，因此会先弹出1。因此，2将在 之前打印1。

显然，由于两种算法存在分歧，这种顺序的变化也会影响其他节点。

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