@dalbio

Как эффективно узнать какие вершины соединенные с вершиной A соединены ребром?

Есть вершина A с ней соединены другие вершины. Моя задача узнать количество пар вершин, которые соединены с вершиной A и соединены между собой. Можно ли это сделать без полного перебора за время n*(n-1), где n-количество вершин соединенных ребром с A?
  • Вопрос задан
  • 113 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
В такой постановке - вряд ли есть что либо эффективнее наивного перебора матрицы смежности или списков инцедентности.

Однако, скорее всего вам не надо считать это количество для одной заданной вершины, а просуммировать по всем (задача вроде - найти сколько в графе треугольников).

В таком случае есть более эффективное решение (хоть и с такой же кубической асимптотикой). Суть в том, чтобы перебирать не вершину треугольника, а ребро. Тогда вопрос будет подсчитать, сколько вершин связанны с заданными двумя. Что равносильно: Найти в скольких столбцах матрицы смежности стоят единицы в двух заданных строках. Это линейный проход, но его можно в 64 раза ускорить, если использовать битовое сжатие. Храните матрицу смежности в битах 64-битных чисел. Т.е. один столбец long long матрицы будет отвечать за 64 столбца. В таком виде можно с-AND'ить два числа и потом подсчитать, сколько в числе единичных бит (что тоже можно сделать сильно быстрее, чем за 64 операции).
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы