从边列表构造邻接列表? [英] Construct an Adjacency List from a List of edges?

问题描述

在图算法的上下文中，通常为我们提供图的方便表示形式(通常作为邻接表或邻接矩阵)以进行操作.

In context of graph algorithms, we are usually given a convenient representation of a graph (usually as an adjacency list or an adjacency matrix) to operate on.

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

My question is, what is an efficient way to construct an Adjacency list from a given list of all edges?

出于这个问题的目的，假设边是元组的列表(如python)，并且(a，b)表示从a到b的定向边.

推荐答案

itertools.groupby的组合(

A combination of itertools.groupby (docs), sorting and dict comprehension could get you started:

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.现在您可以通过adj[1]

This sorts and groups the edges by their source node, and stores a list of target nodes for each source node. Now you can access all adjacent nodes of 1 via adj[1]

这篇关于从边列表构造邻接列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！