如何在networkx.Graph中找到根节点及根节点间路径？

需求1：查找"根节点"（度数为1的叶子节点） #

你描述的"根节点"实际是无环无向图中的叶子节点，即仅连接一条边的节点（度数为1）。通过遍历图中所有节点，筛选出度数等于1的节点即可实现：

# 查找所有度数为1的叶子节点
root_nodes = [node for node in G.nodes if G.degree(node) == 1]
print("根节点（叶子节点）：", root_nodes)

需求2：查找每对根节点之间的路径 #

由于你的图是无环无向图（树结构），任意两个节点之间有且仅有一条唯一路径。为避免重复统计反转路径（如A→B和B→A视为同一条），可使用itertools.combinations生成不重复的根节点对，再通过nx.shortest_path获取每对节点的路径：

import itertools

# 获取所有不重复的根节点对
root_pairs = itertools.combinations(root_nodes, 2)

# 遍历节点对并收集路径
valid_paths = []
for u, v in root_pairs:
    path = nx.shortest_path(G, u, v)
    valid_paths.append(path)
    print(f"路径 {u} → {v}: {path}")

print(f"\n有效路径总数：{len(valid_paths)}")

完整整合代码 #

将上述逻辑嵌入你的现有代码，完整代码如下：

import networkx as nx
import itertools

class PairToNXObject:
    
    def __init__(self, pair):
        self.pair = pair
            
    def __eq__(self, other):
        return hash(self) == hash(other)
    
    def __hash__(self):        
        return hash(f'( {self.pair[0]} {self.pair[1]} )')  # 修正原代码中的//为空格，保证hash与节点表示一致
    
    def __repr__(self):
        return f'( {self.pair[0]} {self.pair[1]} )'
   
coordinateList = [[(1, 2),
                   (3, 4),
                   (4, 5),
                   (5, 6)],
                  [(6, 7),
                   (7, 8),
                   (8, 9),
                   (9, 10),
                   (10, 11),
                   (1, 2)],
                  [(1, 2),
                   (11, 12),
                   (12, 13),
                   (13, 14),
                   (14, 15)]]
    
G = nx.Graph()

for coordinates in coordinateList:
    
    nodes = []
    
    for coordinate in coordinates:
        node = PairToNXObject(coordinate)
        
        G.add_node(node)
        nodes.append(node)
            
    for x in range(0, len(nodes) - 1):
        G.add_edge(nodes[x], nodes[x + 1])
        
# 需求1：查找根节点
root_nodes = [node for node in G.nodes if G.degree(node) == 1]
print("根节点（叶子节点）：", root_nodes)

# 需求2：查找所有根节点对的路径
root_pairs = itertools.combinations(root_nodes, 2)
valid_paths = []
for u, v in root_pairs:
    path = nx.shortest_path(G, u, v)
    valid_paths.append(path)
    print(f"\n路径：{path}")

print(f"\n有效路径总数：{len(valid_paths)}")

nx.draw(G, with_labels=True, node_color='#eeeeee')  

补充说明 #

• 原代码中PairToNXObject的__hash__方法使用了//，属于笔误，修正为空格后可保证节点的哈希值与字符串表示一致，避免节点重复添加的问题。
• 无环无向图（树结构）中，nx.shortest_path返回的就是唯一路径，无需考虑多条路径的情况。
• itertools.combinations确保每对节点只被处理一次，避免重复统计反转路径。

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