如何在NetworkX中按节点名称前缀与度数条件删除节点？

核心思路 #

需要迭代删除满足以下两个条件的节点，直到没有符合条件的节点为止：

1. 节点名称以A或C开头
2. 节点的当前度数 ≤1

删除节点时要同步更新其相邻节点的度数——因为删除操作会降低邻居的度数，可能导致邻居也满足删除条件。最后保留所有两端节点都未被删除的边。

具体实现（Python代码） #

# 原始边列表
raw_edges = [
    "(A2,A1)",
    "(A1,B1)",
    "(B1,C2)",
    "(C2,B2)",
    "(B2,C1)",
    "(B1,A3)"
]

# 解析边，构建邻接表与度数统计
adjacency = {}
node_degree = {}
for edge in raw_edges:
    # 提取边的两个节点
    u, v = edge.strip('()').split(',')
    # 更新邻接表
    adjacency.setdefault(u, set()).add(v)
    adjacency.setdefault(v, set()).add(u)
    # 更新度数
    node_degree[u] = node_degree.get(u, 0) + 1
    node_degree[v] = node_degree.get(v, 0) + 1

# 迭代删除符合条件的节点
while True:
    # 筛选当前待删除的节点
    to_delete = [
        node for node in node_degree
        if (node.startswith('A') or node.startswith('C')) and node_degree[node] <= 1
    ]
    if not to_delete:
        break  # 没有待删除节点，终止循环
    # 处理每个待删除节点
    for node in to_delete:
        # 更新邻居的度数和邻接表
        for neighbor in adjacency[node]:
            node_degree[neighbor] -= 1
            adjacency[neighbor].remove(node)
        # 删除当前节点的记录
        del adjacency[node]
        del node_degree[node]

# 生成最终边列表并去重
final_edges = set()
for u in adjacency:
    for v in adjacency[u]:
        # 统一边的顺序，避免重复记录
        edge_tuple = tuple(sorted((u, v)))
        final_edges.add(f"({edge_tuple[0]},{edge_tuple[1]})")

# 输出结果
for edge in sorted(final_edges):
    print(edge)

代码说明 #

1. 解析边列表：把原始字符串格式的边转换成邻接表（记录每个节点的邻居）和度数统计（记录每个节点的连接数）。
2. 迭代删除节点：循环筛选并删除符合条件的节点，每次删除后同步更新邻居的度数，直到没有可删除的节点。
3. 生成结果：遍历剩余节点的邻接关系，生成无重复的边字符串，按顺序输出。

运行代码后，输出结果与预期完全一致：

(B1,C2)
(C2,B2)

内容的提问来源于stack exchange，提问作者S.Lee