algorithm - 有向图行走 - 至少访问每个节点一次

Question

我熟悉有向图的汉密尔顿路径 - 只访问每个节点一次。

我正在寻找一种算法来遍历图，以便我至少访问每个节点一次。我找不到这个问题的标准名称(如果有的话)。

该图是可步行的 - root-a-d-b-c

这个图是不可步行的 - 因为在我的步行中，如果我到达c，我没有有向边到达a和d，反之，如果我步行到a，d；没有有向边带我去 b 和 c

希望能澄清这个问题吗？这种类型的图行走有标准名称和解决它的算法吗？

• 哈密尔顿路径
• 在图中最多找到 2 个叶子

Answer 1

我不知道是否有一个有向“可步行”图的名称，但确定一个图是否可步行并不难:

1. 使用 Tarjan's algorithn 查找所有强连通分量，例如
2. 制作一个新的 SCC 之间连接的有向图。这将是一个 DAG，当且仅当该 DAG 可步行时，您的原始图才可步行。
3. 要确定 DAG 是否可步行，请执行 topological sort 。然后检查每个顶点是否都有到下一个顶点的边。

每个步骤都需要线性时间，因此整个算法的复杂度为 O(|V|+|E|)。