算法图深度——优先搜索

Question

这是图代码，我想了解深度优先搜索算法，但是我对这段代码遇到了一些问题，

如果我输入参数：

5 5
1 2
1 3
1 5
2 4
3 5

为什么cur在函数dfs中变成了return4比2比1？感谢您的回复

#include <stdio.h>
int book[101], sum,e[101][101];
int n,m,a,b;

void dfs(int cur){
    int i;
    printf("%d ",cur);

    sum++;
    if(sum==n){
        return;
    }

    // 
    for(i=1;i<=n;i++){
        if( e[cur][i]==1 && book[i]==0 ){
            book[i]=1;
            dfs(i);
        }
    }
    return;
}

int main(){
    int i,j;
    scanf("%d %d ", &n,&m);

    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(i==j){
                e[i][j] = 0;
            }else{
                e[i][j] = 99999999;
            }
        };
    };

    for(i=1;i<=m;i++){
        scanf("%d %d" ,&a, &b);
        e[a][b] = 1;
        e[b][a] = 1;
    }

    book[1] = 1;
    dfs(1);
    getchar();
    getchar();
    return 0;
}

Answer 1

我猜你是在问为什么你的 DFS 首先探索 1，然后是 2，然后是 4？嗯，这就是 DFS 的工作原理：它贪婪地转到下一个未访问的顶点。您期望得到什么输出？

关于您的代码的一些说明：

为了改进您得到的答案，我建议发布比您问题中的代码更更清晰的代码：

请使用能告诉读者其含义的变量名称。例如：使用 bool visited[] 而不是 int book[].
使用正确的数据类型！如果要存储边是否存在，或者是否访问了顶点，请使用 bool，而不是一些神奇的 int 值。
全局变量通常不是正确的东西。没有理由为什么你的所有变量都应该是全局的。
数组应该具有恒定大小 101。

算法图深度——优先搜索

Algorithm Graph depth - first search

c

algorithm

graph

depth-first-search