Создайте список смежности из списка ребер?

Question

В контексте алгоритмов графа нам обычно дают удобное представление графика (обычно как список смежности или матрицы смежности) для работы.

Мой вопрос, что является эффективным способом построить список смежности из данного список всех ребер?

Для целей этого вопроса, предположит, что ребра представляют собой список кортежей (как в Python) и (а, б) обозначает направленного края от а до Ь.

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 целевых узлов для каждого источника узел. Теперь вы можете получить доступ ко всем соседним узлам 1 через adj[1]