как решить, связаны ли два человека

Question

Вот проблема:

если два человека зарегистрированы на сайте социальной сети, как решить, подключены они или нет?

мой анализ (после прочтения): на самом деле, вопрос ищем - кратчайший путь от A до B на графике. Я думаю, что здесь работают и алгоритмы BFS, и алгоритмы Дейкстры, а временная сложность одинакова (O (V + E)), потому что это невзвешенный граф, поэтому мы не можем воспользоваться преимуществами очереди приоритетов. Таким образом, простая очередь может решить проблему. Но оба они не решают проблему: найти путь между ними.

Bidrectrol должен быть лучшим решением в этой точке.

Answer 1

Чтобы найти путь между ними, вы должны начать с поиска в ширину. Сначала найдите всех соседей по A, затем найдите всех соседей по всем соседям по A и т. Д. Как только ударил B, у вас есть не только путь от A до B, но у вас также есть кратчайший такой путь.

Алгоритм Дейкстры работает, и вы можете ускорить его, работая с обоих концов, то есть найти соседей по A и соседей по B и сравнить.

Если вы выполняете поиск в глубину, то вы следуете по одному пути за раз. Это будет намного медленнее.

Answer 2

Один из способов - использовать Union Find , добавить все ссылки union(from,to), а если find(A) is find(B) - True, то подключены A и B. Это позволяет избежать рекурсивного поиска, но фактически вычисляет связность всех пар и не дает путей, которые соединяют A и B.

Answer 3

Если вы выполните команду dfs, чтобы определить, подключены ли два человека в социальной сети, то это займет слишком много времени!

Вы уже знаете этих двух людей, поэтому вам следует использовать Двунаправленный поиск. .Но простого двунаправленного поиска будет недостаточно для такого большого графа, как сайт социальной сети.Вам придется использовать некоторые эвристики.На странице Википедии есть несколько ссылок.

Вы также можете использовать поиск A *. Из википедии: "A * использует поиск с лучшим выбором и находит путь с наименьшей стоимостьюот данного начального узла к одному целевому узлу (из одной или нескольких возможных целей). "

Редактировать: Я предлагаю A *, потому что "дополнительная сложность выполнения двунаправленного поиска означает, что алгоритм поиска A * часто является лучшим выбором, если у нас есть разумная эвристика".Итак, если вы не можете сформировать разумную эвристику, используйте двунаправленный поиск.(Формирование хорошей эвристики никогда не бывает легким;).)

Answer 4

Я думаю, что истинный критерий таков: между А и В должно быть как минимум N путей, которые короче, чем К, или А и В соединены напрямую.Я бы пошел с K = 3 и N около 5, то есть 5 общих друзей.

Answer 5

Примечание: ответ отредактирован.

Любой метод может оказаться очень медленным. Если вам нужно сделать это несколько раз, лучше всего найти связанные компоненты графика, после чего задача становится тривиальной операцией O (1): если два человека находятся в одном компоненте, они соединяются.

Обратите внимание, что нахождение подключенных компонентов в первый раз может быть медленным, но их обновление будет обновляться по мере добавления новых ребер / узлов в график.

Существует несколько методов поиска подключенных компонентов.

Один из способов - построить лапласиан графа и посмотреть на его собственные значения / собственные векторы. Число нулевых собственных значений дает вам количество подключенных компонентов. Ненулевые элементы соответствующих собственных векторов дают узлы, принадлежащие соответствующим компонентам.

Другой способ заключается в следующем:

1. Создать таблицу преобразования узлов. Элемент n массива содержит индекс узла, в который преобразуется узел n.

2. Зациклить все ребра (i,j) на графике (обозначая связь между i и j):

   • Вычислить рекурсивно , какой узел преобразует i и j в текущую таблицу. Обозначим результаты как k и l. Обновите запись k, чтобы преобразовать ее в l. Обновите записи i и j, указав также l.

3. Повторно переберите таблицу и обновите каждую запись, указав непосредственно на узел, который рекурсивно преобразуется в.

Теперь узлы в одном подключенном компоненте будут иметь одну и ту же запись в таблице преобразования. Поэтому, чтобы проверить, соединены ли два узла, просто проверьте, не преобразовываются ли они в одно и то же значение.

Каждый раз, когда на график добавляется новый узел или ребро, таблицу преобразований необходимо обновлять, но это обновление будет намного быстрее, чем первоначальный расчет таблицы.