Question

请大侠赐教：用深度优先遍历判断有向图是否存在回路。请写出具体程序。

Answer 1

int dfs(int v)
{
vis[v] = -1;
for(i = 1; i <= n; i++)
{
if(map[v][i] != 0 && !vis[i])
dfs(i);
if(map[v][i] != 0 && vis[i] == -1)
return true;
}
return false;
}

C++的。没写完整的程序，比深度优先遍历多了vis这个数组。因为直接在这里写的，可能有错误还请指正。

追问

有个疑问:如果是个有向无环图的话， if(map[v][i] != 0 && vis[i] == -1 ) return true;
是不是就不行了.

Answer 2

应该会有 ！程序没有....