我熟悉有向图的汉密尔顿路径 - 只访问每个节点一次。
我正在寻找一种算法来遍历图,以便我至少访问每个节点一次。我找不到这个问题的标准名称(如果有的话)。
这个图是不可步行的 - 因为在我的步行中,如果我到达c,我没有有向边到达a和d,反之,如果我步行到a,d;没有有向边带我去 b 和 c
希望能澄清这个问题吗?这种类型的图行走有标准名称和解决它的算法吗?
- 哈密尔顿路径
- 在图中最多找到 2 个叶子
最佳答案
我不知道是否有一个有向“可步行”图的名称,但确定一个图是否可步行并不难:
- 使用 Tarjan's algorithn 查找所有强连通分量,例如
- 制作一个新的 SCC 之间连接的有向图。这将是一个 DAG,当且仅当该 DAG 可步行时,您的原始图才可步行。
- 要确定 DAG 是否可步行,请执行 topological sort 。然后检查每个顶点是否都有到下一个顶点的边。
每个步骤都需要线性时间,因此整个算法的复杂度为 O(|V|+|E|)。
关于algorithm - 有向图行走 - 至少访问每个节点一次,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/75351864/