有向图遍历：求访问所有节点至少一次的路径算法及问题名称

你要找的这种「单条有向路径遍历所有节点至少一次」的问题，标准名称是单路径覆盖（Single Path Cover），它是**路径覆盖问题（Path Cover Problem）**的特殊场景（路径覆盖的一般定义是用最少数量的路径覆盖图中所有节点，单路径覆盖要求路径数为1）。

判断方法与实现思路 #

要确定一个有向图是否存在这类遍历路径，可按以下步骤处理：

1. 强连通分量缩点：把原图中每个强连通分量（SCC，即分量内任意节点双向可达）压缩为单个节点，得到一个有向无环图（DAG）。
2. 验证DAG结构：
   • 仅存在1个入度为0的缩点；
   • 仅存在1个出度为0的缩点；
   • 除首尾两个缩点外，其余所有缩点的入度和出度均为1；
     满足以上条件时，原图就能被单条路径覆盖。
3. 构造遍历路径：从入度为0的强连通分量出发，遍历该分量内所有节点（强连通分量内部可通过任意方式遍历全节点），再沿DAG的边进入下一个分量，重复此过程直至最后一个出度为0的分量，即可得到符合要求的路径。

对应示例说明 #

• 示例1的图缩点后为单个强连通分量（DAG是单节点），满足条件，因此存在遍历路径；
• 示例2的图缩点后会形成多个无法通过单条路径串联的分量（比如{a,d}与{b,c}之间无单向可达路径），不符合DAG的链状结构要求，因此无法完成遍历。

内容的提问来源于stack exchange，提问作者Praveen