图的深度优先遍历能否不用指针来实现。。

乌克大喵喵

学校的一道题
其中dfs函数里用红字部分的是要自己填上去的，一共五个空，想不通为什么最后一句还要往visited数组里写true。
并且第四行和第五行的遍历为什么会错了



#include<stdio.h>
#include<stdbool.h>
#define N 7

const int a[N][N] = {
        {0,1,1,0,0,0,0},
        {1,0,1,1,0,0,0},
        {1,1,0,0,1,0,0},
        {0,1,0,0,1,1,0},
        {0,0,1,1,0,0,1},
        {0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0},
};

int count=0;

void print_path(int n, int path[]) {
       
        for (int i = 0; i < n; i++)
                printf("%d", path[i]);
        printf("\n");

}

void dfs(int step, int goal, int path[], bool visited[]) {
        count++;
        int x = path[step - 1];
        if (x == goal) {
                print_path(step, path);
        }
        else
        {
                for (int i = 0; i < N; i++) {
                        if (a[x][i] == 0)
                                continue;
                        if (!visited[i]) {
                                path[i] = i;
                                visited[i] = true;
                                dfs(i+1, goal, path, visited);
                                visited[i] = true;
                        }
               
                }
        }

}


void traverse(int start, int goal) {
        int path[N];
        bool visited[N];
        for (int i = 0; i < N; i++)
                visited[i] = false;
        path[0] = start;
        visited[start] = true;
        dfs(1, goal, path, visited);
}

int main(void) {
        traverse(0, 6);
        printf("%d", count);
       
        return 0;

}

zltzlt

？

XiaoPaiShen

我也不明白，帮你顶贴。

boqianlv

因为dfs的思想就是，如果前方的路有分叉，那么要先走一条路，然后恢复状态，再走下一条路，如果你不恢复的话，就好比你走迷宫的时候遇到死路了，然后后面掉下来一块石头也把你堵住了没法走，你就被堵死了。这石头就是visited[]=false，你自己用实例去跑一遍代码就懂了。