鱼C论坛

 找回密码
 立即注册
查看: 2263|回复: 3

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

[复制链接]
发表于 2019-8-2 09:41:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
学校的一道题
其中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);
        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] == 0)
                                continue;
                        if (!visited) {
                                path[i] = i;
                                visited = true;
                                dfs(i+1, goal, path, visited);
                                visited = true;
                        }
               
                }
        }

}


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

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

}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-8-2 09:42:30 | 显示全部楼层

回帖奖励 +1 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-10-24 06:12:32 | 显示全部楼层

回帖奖励 +1 鱼币

我也不明白,帮你顶贴。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-1-9 18:16:01 | 显示全部楼层

回帖奖励 +1 鱼币

因为dfs的思想就是,如果前方的路有分叉,那么要先走一条路,然后恢复状态,再走下一条路,如果你不恢复的话,就好比你走迷宫的时候遇到死路了,然后后面掉下来一块石头也把你堵住了没法走,你就被堵死了。这石头就是visited[]=false,你自己用实例去跑一遍代码就懂了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 18:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表