graph - 像这样遍历有向图的算法(内图)

Question

我有一个这样的图表:

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

正如你所看到的，当我们来到 6 时(通过第一个分支，1 → 6)，问题就出现了，所以我们不知道它是什么时候是时候停止并开始遍历另一个分支 (2 → 6)。

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

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

Answer 1

从根本上来说，只有两种方法 traverse a graph .

1. Depth-first search
2. Breadth-first search

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