给定起始节点，求NetworkX无向图的最少重复节点全遍历路径

问题说明 #

给定NetworkX构建的无向图，从指定起始节点出发，要遍历所有节点（顺序不限），目标是找到重复节点最少的路径。

核心逻辑 #

这种问题本质是找图的最小重复遍历路径，关键在于：

• 无向图里，除了起始节点，度数高的枢纽节点往往需要重复访问，用来中转连接其他未访问的节点
• 重复节点的数量完全由图的结构决定，尤其是枢纽节点的位置

示例演示 #

构建示例图 #

import networkx as nx

# 创建含4个节点的无向图
G = nx.Graph()
G.add_nodes_from([1,2,3,4])
# 添加边
G.add_edges_from([(1,2),(2,3),(2,4)])

不同起始点的最优路径 #

• 起始节点为1时，最优路径是 [1,2,3,2,4]
  原因：从1到枢纽节点2，先走完3，再回到2去走4，只重复访问了2一次
• 起始节点为3时，最优路径可以是 [3,2,1,2,4] 或者 [3,2,4,2,1]
  原因：从3到枢纽节点2，依次遍历剩下的节点，同样只重复访问2一次

通用解法思路 #

对任意无向图，要得到这类最优路径，可以这么做：

1. 先找出图里的割点（枢纽节点）：这类节点是连接多个子区域的关键，一般都得重复访问
2. 以起始节点为起点，用DFS或BFS的变种，优先去走没访问过的节点，只有需要中转的时候才重复走枢纽节点
3. 构建路径时，记录已经访问过的节点，当当前节点的所有邻接未访问节点都走完后，回溯到最近的枢纽节点，继续处理剩下的未访问节点

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