Question

无向图的深度优先遍历

void DFS (graph *g, int i )
{ int j ; int visited[n];
for ( j = 0; j< n; j++ )
visited [j] = 0;
printf("node:%c\n",g->vexs[i]);
visited[i]=1;
for ( j= 0; j<n; j++ )
if (g->arcs[i][j]==1&&( ! visited[j] ))
DFS (g,j);
}

介个函数好像不对，结果是两个结点无限交替输出，请问错在哪？

Answer 1

for ( j = 0; j< n; j++ )
visited [j] = 0;

这段是什么意图？ 如果是要把所有节点的visited设置为false的话，应该在DFS函数之外做。因为这是初始化操作，否则你每次递归调用DFS，都会先把所有visited清空，这样你就永远没有访问过的节点了。