Блог

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


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


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

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

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

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

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

 nodes = (~rowP)*rowQ';
  

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