从边列表构造邻接表？

Question

在图算法的上下文中，我们通常会得到一个方便的图表示形式（通常作为邻接列表或邻接矩阵）进行操作。

我的问题是，从给定的所有边列表构造邻接列表的有效方法是什么？

出于该问题的目的，假设边是元组列表（如在 python 中），并且 (a,b) 表示从 a 到 b的有向边。

Answer 1

itertools.groupby( docs )、排序和理解的结合dict可以帮助您入门：

from itertools import groupby

edges = [(1, 2), (2, 3), (1, 3)]

adj = {k: [v[1] for v in g] for k, g in groupby(sorted(edges), lambda e: e[0])}
# adj: {1: [2, 3], 2: [3]}

这按源节点对边进行排序和分组，并list为每个源节点存储目标节点。现在你可以访问1via的所有相邻节点adj[1]