Алгоритм поиска т-друзей узла

Question

У меня есть следующее упражнение, где у меня есть социальный график, смотрите ниже.Из моего понимания, если t = 2 и у нас есть p = H , тогда результат будет равен O и B .

Это пониманиеправильно?

Answer 1

Выполните поиск в ширину из исходной точки. Когда вы ставите точку в очередь, также ставьте в очередь расстояние от начала координат. Ограничьте расстояние до t, не ставя точку в очередь с расстоянием более t. Набор посещенных узлов является решением.

Вы посещаете каждую вершину не более одного раза, вы посещаете каждое ребро не более одного раза. Сложность O(E).