Можно ли выполнить поиск в ширину с массивом соседей?

Question

Входные данные программы таковы:

1 2
2 3
2 5
5 1
3 4
4 5
4 6

Первое число представляет вершину один, второе число представляет вершину 2. Это означает, что существует ребро, соединяющее две вершины, то есть они являются соседями. 1 [Мой вопрос: возможно ли выполнить BFS, используя только список соседей? Или мне нужно преобразовать данные в график?

Буду признателен за любую помощь!

Answer 1

Простейшим способом go было бы построить граф и использовать доступные алгоритмы. В экземпляре NetworkX foe у вас есть набор базовых c алгоритмов для в ширину поиска узлов графа в nx.algorithms.traversal. Таким образом, вы можете сделать:

s = '''1 2
2 3
2 5
5 1
3 4
4 5
4 6'''

l = [i.split() for i in s.splitlines()]

Затем построить график из списка ребер:

import networkx as nx

G = nx.from_edgelist(l)

И использовать доступные методы из упомянутого модуля, такие как перебор ребер по ширине. -первый поиск, начиная с источника:

list(nx.algorithms.traversal.breadth_first_search.bfs_edges(G, '2'))
# [('2', '1'), ('2', '3'), ('2', '5'), ('3', '4'), ('4', '6')]

Answer 2

Можно ли выполнить BFS, используя только список соседей?

список соседей - идеальный вход для проблем BFS.

(мы называем это список смежности)

преобразование списка в граф или нет - это вопрос интерпретации.

вы можете кодировать BFS со списком, используя векторы или некоторые другие простые структуры данных,

без явного преобразования списка в некоторый «класс графа» или что-то в этом роде.

но вам будет легко нарисовать концептуальный граф для проверки входных и выходных данных.