Question

有向图的遍历算法和无向图一样吗

无向图的深度遍历算法使用栈实现的，如果一个节点没有可以访问的节点了，就得出栈，访问上一个节点没有访问过的节点。那么对于有向图来讲，是不是也可以出栈访问上一个节点没有访问过的节点呢？还有什么别的规则或者区别吗？（有些难懂，请高手帮忙啊！）

Answer 1

有向图的深度遍历与无向图的是一样的。

Answer 2

static int countOfWays = 0;
int traverseForNum(vertex* sourceBuf, vertex* targetBuf){
int i = 0;
if (sourceBuf->searched){
return 1; /* already searched */
}else{ /* not searched yet */
sourceBuf->searched = 1;
for ( i = 0; i < sourceBuf->numOfGoing; i ++ ){
if(sourceBuf->goingVertex->[i] == targetBuf){
countOfWays ++;
}
}
for ( i = 0; i < sourceBuf->numOfGoing; i ++ ){
if(sourceBuf->goingVertex->[i] != targetBuf){
traverseForNum(sourceBuf->goingVertex[i]), targetBuf);
}
}
}
return 1;
}

如下是顶点的定义：
typedef struct buf vertex;
struct buf{
vertex **goingVertex; /* vertex out the current */
vertex **comingVertex; /* vertex into the current */
int numOfGoing; /* count of vertex going list */
int numOfComing; /* count of vertex coming list */
int searched; /* flag used to search for the graph */

};

代码我以前调试过，完全OK。
但是你给我的这个题目，我是基于以前的代码给你修改的，C99下即使调试不通过问题也不太大，你稍微修改一下就好。但是我有需要说明的：这个是做出你问的第一个问题的答案；第二个问题，我想可能跟乘法定律有关，可以用j到i的路径数目乘以i到k的路径数目，算法我想了一下，如果非要用一个遍历作出来，还真要花点儿时间，还不一定最优。

Answer 3

看下算法导论，那里面用的顶点染色，对有向图、无向图处理是一样的。