如何找到用户的朋友（两条边的最短路径）的数量？
How to find the number of friend-of-friend (shortest path of two edges) to a user?
假设给定一个图 G = (V,E)，其中 V 是一组用户，如果用户 v 和 w 是朋友，则 E 中的边 (v,w)。
那么，如何编写算法来查找用户的好友连接数？它的 big-O 估计怎么样？
我想我可以使用多少个 v 有两条边的最短路径到用户，但我不知道具体如何处理。
创建一组与第一个顶点相邻的顶点。 （例如使用哈希进行查找 O(1)。对于与第二个相邻的每个顶点，检查它是否与第一个相邻。
这将需要 space O(E1) 和时间 O(E1 + E2) 其中 E1 和 E2 是每个顶点的边数。
简单的广度优先搜索会比较慢，因为对于从 E1 找到的每个顶点，您需要依次查看它的所有边。如果我们平均每个顶点 n 条边，则应为 O(n^2)。但在实践中，情况比这更糟。大多数人并没有超级连接，但认识一个超级连接的人。那些超级连接的人可以快速添加很多优势。
假设给定一个图 G = (V,E)，其中 V 是一组用户，如果用户 v 和 w 是朋友，则 E 中的边 (v,w)。
那么，如何编写算法来查找用户的好友连接数？它的 big-O 估计怎么样？
我想我可以使用多少个 v 有两条边的最短路径到用户，但我不知道具体如何处理。
创建一组与第一个顶点相邻的顶点。 （例如使用哈希进行查找 O(1)。对于与第二个相邻的每个顶点，检查它是否与第一个相邻。
这将需要 space O(E1) 和时间 O(E1 + E2) 其中 E1 和 E2 是每个顶点的边数。
简单的广度优先搜索会比较慢，因为对于从 E1 找到的每个顶点，您需要依次查看它的所有边。如果我们平均每个顶点 n 条边，则应为 O(n^2)。但在实践中，情况比这更糟。大多数人并没有超级连接，但认识一个超级连接的人。那些超级连接的人可以快速添加很多优势。