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