Python中基于节点值合并列表实现图邻接表结构

问题背景 #

输入格式：首行是边的数量，后续每行是一条边的两个节点ID。示例输入：

3
0 1
0 2
1 2

现有解析及Networkx建图代码：

E = int(input())
lst = []
lst_ = []

for x in range(E):
    l, q = map(int, input().split())
    lst.append(l)
    lst_.append(q)

import networkx as nx
G = nx.Graph()
for x in range (len(lst)):
    G.add_edge(lst[x],lst_[x])

需要将图转为邻接表形式的嵌套列表，示例输出：

mega_lst = [[1,2],[0,2],[0,1]]

简便实现方案 #

方案1：字典构建邻接关系转嵌套列表 #

无需额外依赖，先通过字典收集每个节点的邻居，再按节点ID顺序生成列表：

E = int(input())
adj_dict = {}
all_nodes = set()

for _ in range(E):
    u, v = map(int, input().split())
    # 无向图双向添加邻居
    adj_dict.setdefault(u, []).append(v)
    adj_dict.setdefault(v, []).append(u)
    all_nodes.update({u, v})

# 按节点ID升序生成邻接表
max_node = max(all_nodes)
mega_lst = [adj_dict.get(node, []) for node in range(max_node + 1)]

print(mega_lst)

注：若节点ID不连续，可根据需求调整列表生成逻辑，比如只保留存在的节点对应的子列表。

方案2：直接用列表索引映射节点ID #

适合节点ID从0开始连续的场景，先确定节点总数，初始化空邻接表后逐个添加邻居：

E = int(input())
max_node = -1
edges = []

# 先遍历一次获取最大节点ID
for _ in range(E):
    u, v = map(int, input().split())
    edges.append((u, v))
    max_node = max(max_node, u, v)

# 初始化邻接表并填充
mega_lst = [[] for _ in range(max_node + 1)]
for u, v in edges:
    mega_lst[u].append(v)
    mega_lst[v].append(u)

print(mega_lst)

方案3：利用Networkx直接导出邻接表 #

如果已经使用Networkx，可直接通过库方法生成邻接表，代码更简洁：

import networkx as nx

E = int(input())
G = nx.Graph()
for _ in range(E):
    u, v = map(int, input().split())
    G.add_edge(u, v)

# 按节点ID排序后生成邻接表
sorted_nodes = sorted(G.nodes())
mega_lst = [list(G.neighbors(node)) for node in sorted_nodes]

print(mega_lst)

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