В GRPAH, какой будет самый быстрый способ найти все узлы, подключенные к одному узлу, но не подключенные к другому узлу.?

Question

Скажем, у вас есть два узла P и Q. Теперь мы должны найти узлы, имеющие ребро с Q, но не с P. Каков самый быстрый способ сделать это?Какой алгоритм или структуру данных я должен использовать?В настоящее время при добавлении ребра я поддерживаю вектор с каждым узлом, который сохраняет все узлы, связанные с этим узлом (давайте назовем это Vi для i-го узла).Также у меня есть матрица смежности.Примерно как то так я и делаю.

for each node in Vq<br> check if it is connected to P using adjacency matrix<br> do something with this node<br>

Как вы думаете, здесь можно сделать что-нибудь быстрее?

Answer 1

Поправьте меня, если я не прав, но он должен работать не быстрее, чем по линейному времени. Каждый узел должен быть проверен, но существование ребра проверяется в постоянном времени.

Answer 2

Почти то же самое:

• Возьмите строку P и строку Q из матрицы смежности
• Для узла I
  • , если ястолбец имеет 0 в строке P и 1 в строке Q, выполните операцию.

Это явно означает, что в цикле for нет другого цикла для проверкиесли он подключен ".

Это самое быстрое, что вы можете сделать теоретически (это O (n), а теоретическая нижняя граница - O (n)).На практике вы можете оптимизировать его в зависимости от того, какой язык вы используете и для чего он оптимизирован.Например, Matlab понравится, если вы сформулируете это как:

nodes = (~rowP)*rowQ';