寻找节点的t友的算法 [英] Algorithm for finding t-friends of node

问题描述

我进行以下练习，下面是一个社交图。根据我的理解，如果 t = 2 并且我们具有 p = H ，那么结果将等于 O和B 。

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.

这种理解正确吗？

推荐答案

从原点开始进行广度优先搜索。当您使一个点入队时，也要使其与原点的距离也入队。通过不使距离大于 t 的点入队，将距离限制为 t 。被访问的节点集就是解决方案。

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.

您最多可以访问每个顶点一次，最多可以访问每个边缘一次。复杂度是 O（E）。

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

这篇关于寻找节点的t友的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！