Хорошим инструментом для визуализации проблем с графами является graphviz, который поставляется с командой dot. Сначала создайте edgelist.dot, содержащий все ребра из вашей переменной edgeList:
digraph G {
0 -> 1
0 -> 2
1 -> 0
1 -> 3
2 -> 0
2 -> 4
2 -> 5
3 -> 1
4 -> 2
4 -> 6
5 -> 2
6 -> 4
}
(есть более короткие способы написать это, что вы можете посмотреть).
Тогда кормите его через dot:
c:\srv\tmp> dot -Tsvg -o edgelist.svg edgelist.dot
, а затем откройте созданный edgelist.svg файл:
Списки смежности - это списки узлов, к которым можно обратиться из определенного узла, например, для узла 0 имеются стрелки к узлам 1 и 2, поэтому adjacencyList[0], т. е. список смежности для узла 0 должен быть [1, 2].
Аналогично, стрелки-выходы из узла 2 достигают узлов 0, 4 и 5, поэтому adjacencyList[2] должно быть [0, 4, 5].
Вручную, проходя каждый узел по порядку, список смежности заканчивается:
[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]
^ ^ ^ ^ ^ ^ ^
item/index: 0 1 2 3 4 5 6
В вашем коде эта строка:
adjacencyList = [[] for vertex in vertexList]
просто создает adjacencyList как список пустых списков ([]) с длиной, равной количеству вершин.
Тогда это для цикла:
for i in edgeList:
adjacencyList[i[0]].append(i[0])
пытается заполнить его. Чтобы увидеть, что не так, мы можем переписать цикл for, чтобы он распаковывал ребра в edgeList:
for (start, end) in edgeList:
adjacencyList[start].append(..?..)
очевидно, что ..?.. должно быть end и не начинаться:
for start, end in edgeList:
adjacencyList[start].append(end)
Теперь вы можете видеть, что цикл for выполняет то, что мы делали выше, для каждого ребра (start, end) добавляет end в список смежности start.
Приложение: Ваш код хорошо работает для случаев, когда вершины (0, 1 и т. Д.) Имеют те же значения, что и индексы в массиве. Хотя это эффективно, оно не может быть педагогически предпочтительным (или, может быть, я не знаю ;-) В любом случае, если мы переименуем ваши вершины так, что 0 станет "A", 1 станет "B" и т.д., вам нужно будет использовать другую структуру данных для списка смежности, например:
from collections import defaultdict
edgeList = [("A", "B"),
("A", "C"),
("B","A"), ("B","D"),
("C","A"), ("C","E"), ("C","F"),
("D","B"),
("E","C"), ("E","G"),
("F","C"),
("G","E")]
adjacencyList = defaultdict(list)
for start, end in edgeList:
adjacencyList[start].append(end)
print(sorted(adjacencyList.items()))
который печатает:
[('A', ['B', 'C']), ('B', ['A', 'D']), ('C', ['A', 'E', 'F']), ('D', ['B']), ('E', ['C', 'G']), ('F', ['C']), ('G', ['E'])]
означает, что список смежности для 'A' равен ['B', 'C'] и т. Д.
возможно (и, возможно, полезно для времени выполнения) перевести эту версию в первую версию (особенно в языках, более статичных, чем Python).