0847. Shortest Path Visiting All Nodes ======================================================================================================================== 题目信息 -------- :题号: 0847 :难度: Hard :主题: 无向图、覆盖所有节点、最短路径 :原题: `LeetCode 0847 `_ :重点: 路径可从任意节点开始、在任意节点结束,并允许重复经过节点和边;目标是至少访问每个节点一次的最少边数 题目重述 -------- 给定一个连通无向图的邻接表 ``graph``,节点编号为 ``0`` 至 ``n - 1``。需要选择任意起点沿图中的边行走,直到所有节点都至少被访问一次。 行走过程中可以多次经过同一个节点或同一条边,终点也没有限制。路径长度按经过的边数计算。请返回访问全部节点所需的最短路径长度。 ``1 <= n <= 12``,每个邻接表长度小于 ``n``;图没有自环,邻接关系对称,输入保证图连通。 自建示例 -------- 分叉树中需要重复经过连接节点: .. code-block:: text 输入:graph = [[1],[0,2,3],[1],[1,4],[3]] 输出:5 解释:可以从节点 2 出发,依次走 2 -> 1 -> 0 -> 1 -> 3 -> 4,共经过 5 条边并访问全部节点。节点 1 必须被重复经过才能兼顾叶节点 0、2 与通向 4 的分支;不存在只走 4 条边且覆盖五个节点的哈密顿路径。 图只有一个节点: .. code-block:: text 输入:graph = [[]] 输出:0 解释:n 达到题目允许的最小值。任选的起点已经访问了图中的唯一节点,不需要经过任何边,因此最短路径长度为 0。