Оптимизированный поиск. Как уменьшить сложность?

Question

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

Пусть говорят, что мы должны пройти в чьих-сетях - друзья, друзья друзей (ФОФ) и FoFoF (1-й, 2-й, 3-й степень .. до 6 степени) до поиска конкретной вещи, скажем, «люди, живущие в Калифорнии». Задача проблемы значительно возрастает, когда у вас 1000 друзей , а ваши 1000 друзей имеют 1000 друзей и т. Д.

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

Программа, которую вы отправляете, должна вернуть степень, с которой это лицо связано с вами. [где «конечный узел» - это ваша степень 1 (друг) или вторая (друг друга) или 3-я степень (FoFoF) или степень больше, чем 3-я степень].

Answer 1

Предполагая, что ваш график невзвешен, выполнение Breadth First Search даст вам кратчайшие пути (которые фактически являются степенями, которые вам нужны). Если назначение известно, вы также можете использовать Алгоритм Дейкстры, чтобы найти кратчайший путь к этому конкретному узлу, хотя, если граф невзвешен, просто выполнение BFS будет более эффективным, так как его сложность ниже, чем у Dijkstra. Также, если я правильно понимаю, ваш выход должен охватывать только 4 случая: степени 1,2,3 или выше. Если это так, вы можете просто BFS первые три уровня и сохранить результаты. Затем вы можете ответить на вопрос в течение постоянного времени, проверяя наличие такого лица в данных, полученных через BFS.