BFS или DFS для социальной сети следуют модели

Question

Я пытаюсь реализовать график последователей социальной сети.

Требование таково, что для простоты мы можем считать, что профиль каждого пользователя u в графе будет представлен положительным целочисленным значением P [u]. Меня просят предоставить службу знакомств. Цель состоит в том, чтобы создать хорошего партнера для знакомств для каждого пользователя u. Партнер хорош, если этот человек доступен через цепочку следования, профиль которой точно такой же, как и (если есть).

Это проблема обхода графика, я могу реализовать ее сам, но вопрос здесь в том, что я не уверен, что в этом случае лучше использовать DFS или BFS?

Answer 1

С точки зрения сложности оба алгоритма работают в O (V + E). Хотя с точки зрения пространства памяти DFS лучше, чем BFS. Поэтому, если вы заботитесь о памяти, DFS будет лучше для вас. Отложив память в сторону, вы должны знать только, какие алгоритмы работают лучше всего для вас. Например, вы можете предпочесть хороший партнер, который ближе к пользователю по сравнению с другими партнерами. У пользователя может быть много хороших партнеров. Поэтому, если вы хотите найти хорошего партнера, который ближе сначала, BFS сделает это за вас. В противном случае нет никакой разницы. Глядя на пример ниже, DFS (1) может вернуть 8 или 7 в качестве хорошего партнера для 1. При запуске BFS (1) вы всегда получите 7 первых в качестве хорошего партнера для 1.