C语言中DFS无法遍历全部节点的问题排查求助

问题代码与现象 #

DFS函数实现 #

void DFS(int v, int *visited, int A[20][20],int satir){
    printf("\n%d visited",v+1);
    // Create a queue to store nodes to visit
    int i;
    // Mark the start node as visited and enqueue it
    visited[v] = 1;
    // While there are nodes in the queue
    for(i=0;i<satir;i++){
        if (A[v][i]==1 && visited[i]==0){
            DFS(i,visited,A,satir);
        }
    }
}

调用方式 #

DFS(0,&visited,Tmp,satir/2);

邻接矩阵（12个节点，索引0-11） #

{0,1,1,0,1,0,0,0,0,0,0,0},
{1,0,1,0,0,0,0,0,0,0,0,0},
{1,1,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,0,1,1,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1,1,0},
{0,0,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,1,0,1,1,0}

程序输出 #

1 visited
2 visited
5 visited
6 visited
8 visited
7 visited

问题根源 #

核心问题出在调用DFS时传入的satir/2参数：
你的邻接矩阵包含12个节点（索引0到11），但satir/2会把循环上限限制为6（假设satir原本是12），导致DFS函数里的for(i=0;i<satir;i++)只会检查当前节点与前6个节点（索引0-5）的邻接关系，完全忽略了后面6个节点（索引6-11）的连接。

比如节点8（对应索引7）的邻接节点是9、10、11（索引8、9、10），但因为循环只到i<6，根本不会遍历到这些索引，所以后续节点无法被访问，自然无法完成全图遍历。

另外，函数里的注释写了“Create a queue”，这是BFS的逻辑注释，和DFS递归实现不符，但这只是注释错误，不影响功能。

修复方案 #

1. 修正调用参数：把satir/2改为完整的节点数satir，确保循环能遍历所有12个节点的邻接关系：

DFS(0, visited, Tmp, satir);

注意：&visited应该直接写visited，因为数组名本身就是指向首元素的指针，不需要取地址。

2. 确保visited数组初始化正确：调用DFS前，必须将visited数组的所有元素初始化为0，避免节点被误判为已访问。

修复后，DFS会从节点0出发，完整遍历所有连通节点，最终覆盖所有12个节点。

内容的提问来源于stack exchange，提问作者user19224948