Создание списка смежности из файла

Question

Мне было поручено прочитать содержимое файла, а затем создать список смежности.

Каждая строка представляет собой ребро в графе, и файл выглядит следующим образом:

0 1 
2 1 
0 2 
1 3 

До сих пор я прочитал все, что в и теперь есть список, который включает в себя:

[[ '0', '1'], ['2', '1'], ['0', '2'], ['1', '3']]

Мой вопрос: как сделать Я использую приведенное выше, чтобы получить список смежности, который выглядит следующим образом:

[[1; 2]; [0; 2; 3]; [1; 0]; [1]]

Обратите внимание: очень новичок в языке Python, и мне не разрешено импортировать что-либо.

Answer 1

Следующее решение использует dictionary:

l = [['0', '1'], ['2', '1'], ['0', '2'], ['1', '3']] 
adjacencies = dict() 
for edge in l: 
    x, y = int(edge[0]), int(edge[1]) 
    if x not in adjacencies: adjacencies[x] = set() 
    if y not in adjacencies: adjacencies[y] = set() 
    adjacencies[x].add(y) 
    adjacencies[y].add(x) 
print([sorted(adjacencies[_]) for _ in sorted(adjacencies)]) 

Однако более элегантное решение было бы построить словарь adjacencies непосредственно во время синтаксического анализа входного файла (test.txt в следующем примере):

def get_adjacency_list(filename): 
    adjacencies = dict() 
    with open(filename) as infile: 
     for line in infile: 
      x, y = [int(_) for _ in line.strip().split()] 
      if x not in adjacencies: adjacencies[x] = set() 
      if y not in adjacencies: adjacencies[y] = set() 
      adjacencies[x].add(y) 
      adjacencies[y].add(x) 
    return [sorted(adjacencies[_]) for _ in sorted(adjacencies)] 

print(get_adjacency_list('test.txt')) 

Обратите внимание, что значения словаря adjacencies имеют тип set, которые преобразуются в списки из-за сортировки (через встроенный метод sorted()).

IF Вам будет разрешено импортировать все, что вы должны использовать defaultdict вместо обычных словарей Python.