Алгоритм - Друг друга

Question

Я просто изучаю теорию графов, и я пытаюсь написать код для проблемы с алгоритмом. Проблема включает в себя n группа людей, каждая из которых имеет хотя бы одну взаимную дружбу с одним из членов. Проблема заключается в том, чтобы найти кратчайшую связь между двумя людьми. Самая короткая связь дружбы содержит наименьшее количество людей. Например; A и B являются общими друзьями, а B и C являются общими друзьями, если A и C являются общими друзьями, тогда A-C и A-B-C являются связями между A и C, но A-C считается короче, потому что он включает в себя меньших людей.

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

Answer 1

Для невзвешенной проблемы кратчайшего пути из двух узлов - вы можете делать с BFS, не нужно для Dijkstra's algorithm, что сложнее реализовать и менее эффективно.

Обратите внимание, что основной проблемой BFS является эффективность пространства, поскольку она работает в пространстве O(|V|), ее можно частично решить с помощью компиляции с DFS, называемой Iterative Deepening DFS. Он также будет оптимальным, но будет потреблять меньше места (за счет дополнительного времени).

---

Это, кажется, не быть, но если вы можете оценить, насколько близко вы от цели - вы можете использовать A* Algorithm, который дается хороший heuristic function, скорее всего, работать быстрее.

Также обратите внимание: Если вы хотите кратчайшее расстояние между всеми пользователями, вы можете использовать Floyd-Warshall's algorithm