Алгоритм поиска цепочки друзей для пользователей соцсети

[wataru]

Ох… Давно я не видел такой ужасной реализации обхода в ширину.

Похоже, вам удалось реализовать линейный алгоритм за куб! Если в графе 1000 вершин, то ваш алгоритм работает в миллион раз медленнее, чем должен. Если в графе 10000 вершин — то в 100 миллионов раз медленнее. Поздравляю! Это надо очень постараться.

можно заметить момент, который оптимизирует алгоритм

И вам при этом хватает наглости что-то говорить про оптимизацию.

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

Хотя, справедливости ради, что-то да вы и понимаете. Вот из-за этого "могут встретиться не один раз" у вас в N раз больше проверок. Еще в N раз больше — ваше непонимание, как работают структуры данных. Вместо деланья union и intersection на списках, вам стоило бы использовать set с add и in.

Перечитайте хотябы статью на википедии, на которую дали ссылку в начале. И оттуда ссылку на обход в ширину.
Перепишите алгоритм с использованием очереди, как и написано в любой статье про обход в ширину, и помечайте сами вершины, как посещенные, а не храните где-то список всех посещенных вершин.

[arsen_zaharenko]

не понимаю следующие замечания:
1. почему вы решили, что алгоритм сводится к линейной сложности?
2. почему вы решили, что граф задан изначально? смысл задачи в том, чтобы достраивать поочерёдно уровни пользователей и стараться найти пересечения последних уровней, что и даёт промежуточного "общего знакомого" (пользователя M) и т.д.
3. почему вы решили, что если я указал двунаправленный поиск, то я и должен его реализовывать? была использована идея "двунаправленности", а не поиск в ширину в графе

с замечанием по замене list на set согласен

[wataru]

1) Википедия, ссылка про двунаправленный поиск, которую вы дали:

Сложность всего алгоритма оценивается как сумма сложности прямого и обратных поисков, проверки принадлежности, равной одной операции, постоянному времени (O(n))

Если вы не знаете про ассимптотическую сложность, то вот это вот непонятное O(n) — это и есть линейная сложность.

2) Без разницы, как у вас задан граф. Изначально весь, или вы можете получать соседей заданной вершины — алгоритм от этого не меняется. Поиск в ширину (путь и двунаправленный) исследует соседей уже посещенных вершин.

3) Ну вы сами написали, что разрабатываете вариант двунаправленного поиска в ширину:

Вот только никакого алгоритма и его реализации я не обнаружил, поэтому решил разработать свой вариант алгоритма.

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