Algorithm for finding t-friends of node

问题:

I have the following exercise where I have a social graph look below. From my understanding if t = 2 and we have p = H then the result would be equal O and B.

Is this understanding correct?

回答1:

Do a breadth-first search from the origin point. When you enqueue a point, also enqueue the distance from the origin. Limit the distance to t by not enqueueing point with a distance more than t. The set of visited nodes is the solution.

You visit each vertex at most once, you visit each edge at most once. Complexity is O(E).