Я следую учебному пособию по матрицам смежности и спискам для графов. Очень ясно, как проверить, соединены ли два узла в матрице смежности.
Вы просто:
vector<vector<bool>> adjMatrix(5);
add_edge(1, 2, adjMatrix);
if (adjMatrix[1][2])
cout << "edge exists";
И это явно O (1) сложность.
Однако Я не понимаю, как добиться того же с помощью списка смежности.
vector<list<int>> adjacencyList(vertices+1);
adjacencyList[1].push_back(2);
Если у меня есть несколько вершин в списке, я должен был бы выполнить итерацию и проверить с помощью оператора if, если какая-то ссылка существует. Это кажется абсурдно неэффективным.
Может ли кто-нибудь помочь мне обернуть голову вокруг этого?