像这样遍历有向图的算法（内图）

Question

我有一个像这样的图表：

一个简单的规则：
图中的每个节点只知道其后继节点。

正如你所看到的，当我们来到 6 时（通过第一个分支，1 → 6），问题发生了，因此我们不知道什么时候该停止并开始遍历另一个分支 (2 → 6)。

有人可以建议一种遍历这样的图的算法吗？

当我遍历 1 → 6 → end of graph，然后返回到 2 → 6 时，我想到了这个想法。
但我认为这不是一个好主意，因为在 1 → 6 → end of graph 方式上可能会有很多分叉。

Answer 1

从根本上来说，只有两种遍历图的方法。

1. 深度优先搜索
2. 广度优先搜索

当然，还有很多其他选项，但这些是最简单且最普遍适用的。无论如何，其他算法大多可以被认为是这些主题的变体。选择最适合您问题的一项，然后进城！

Answer 2

递归地，当你穿过每个节点时，你会标记它，当没有什么可以探索时，你会返回。

类似于

function 

mark the current edge
for all it's vertices
call the function on the edge that is connected with the vertice if the edge is not marked
do something with the edge (display or whatever)
once there is no vertices left return 

C 示例，如果图由相邻矩阵表示，长度为 1000 意味着没有顶点。

void inDepth(int i)
{
    int j;

    edges[i] = 1; //edges is the marking vector

    for (j=0; j<N; j++)
    {
        if ((vertices[i][j]<1000) && (vertices[i][j]>0) && (edges[j]==0)) 
        {
            inDepth(j); 
        }
    }

    printf("%d ",i);
}

Answer 3

这不是DFS搜索吗？ （深度优先搜索）