Question

问一个关于图的深度优先遍历算法实现的问题

void MGraph::DFSTraverse(int v)
{
cout<<vertex[v];visited[v]=1;
for(j=0;j<vertexNum;j++)
if(arc[v][j]==1&&visited[j]==0)DFSTraverse(j);
}
这是书上的深度优先遍历算法的代码，不知道有错么？
可是我自己动手解这个算法的时候这个j的变量感觉很有问题啊，是我理解的问题么？
求大神解答

Answer 1

不知道你看的是什么书，代码也只能猜测一下：

//遍历vertex
void MGraph::DFSTraverse(int v)
{
// 输出当前vertex， 并设为已遍历
cout<<vertex[v];visited[v]=1;

// 对所有vertex进行测试
for(j=0;j<vertexNum;j++)
// 如果vertex[j] 和当前的vertex有边相连，并且没有访问过，递归遍历vertex[j]
if(arc[v][j]==1&&visited[j]==0)DFSTraverse(j);
}

从递归关系来看，就是从一个vertex，找和它有边相连的vertex进行遍历，因此，是深度优先遍历。