深度优先搜索算法为什么不能用循环实现

Question

题目描述
深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。其过程为：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。其算法可以描述如下：
在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。
输入格式
输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。
输出格式
只有一行，包含n个整数，表示按照题目描述中的深度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。
样例输入
4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0
样例输出
0 1 3 2

这是网上找的正确的深度优先搜索算法

#include<stdio.h>
#define maxint 32767
#define mvnum 100
typedef int vertextype;
typedef int arctype;
typedef struct{
    vertextype vexs[mvnum];
    
    arctype arcs[mvnum][mvnum];
    
    int vexnum;
}amgraph;
void creat(amgraph *G)
{
    scanf("%d",&G->vexnum);
    
    for(int i=0;i<G->vexnum;i++)
    {
        G->vexs[i]=i;
    }
    
    for(int i=0;i<G->vexnum;i++)
    for(int j=0;j<G->vexnum;j++)
    G->arcs[i][i]=maxint;
    
    for(int i=0;i<G->vexnum;i++)
    for(int j=0;j<G->vexnum;j++)
    scanf("%d",&G->arcs[i][j]);
 } 
int visited[mvnum]={0};
void DFS(amgraph G,int i)
{
    visited[i]=1;
    printf("%d ",G.vexs[i]);
    
    for(int j=0;j<G.vexnum;j++)
    {
        if(G.arcs[i][j]==1&&!visited[j])
        DFS(G,j);
    }
}
void DFStraverse(amgraph G)
{
    for(int i=0;i<G.vexnum;i++)
    {
        if(!visited[i])
        DFS(G,i);
    }
}
int main()
{
    amgraph G;
    creat(&G);
    DFStraverse(G);
    return 0;
}

这是我写的错误方法

#include<stdio.h>
#define max 10000
typedef struct{
    int dingdian[max];
    int guanxi[max][max];
    int dingdianshu;
}tu;
void creat(tu *t)
{
    scanf("%d",&t->dingdianshu);
    
    for(int i=0;i<t->dingdianshu;i++)
    {
        t->dingdian[i]=i;
    }
    
    for(int i=0;i<t->dingdianshu;i++)
    for(int j=0;j<t->dingdianshu;j++)
    scanf("%d",&t->guanxi[i][j]);
}
int visited[max]={0};
void DFS(tu t,int i)
{
    printf("%d",t.dingdian[i]);
    visited[i]=1;
    for(;i<t.dingdianshu;i++)
    for(int j=0;j<t.dingdianshu;j++)
    {
        if(t.guanxi[i][j]==1&&!visited[j])
        {
            i=j;
            DFS(t,i);
        }
    }
}
int main(void)
{
    tu t;
    creat(&t);
    int i=0;
    DFS(t,i);
    return 0;
}

为什么`使用循环实现深度优先搜索的时候程序会不能运行？

Answer 1

你的代码

for (; i < t.dingdianshu; i++)
    for (int j = 0; j < t.dingdianshu; j++)
    {
        if (t.guanxi[i][j] == 1 && !visited[j])
        {
            i = j;
            DFS(t, i);
        }
    }

感觉内循环里面有问题，i = j来更新i的值，循环条件就不满足了，递归调用后，外层的就会一直+，一直循环，死循环了。