如何判断两个人是否连接

假设两个人在社交网站上注册，如何判断他们是否连接？

我的分析（阅读更多后）：实际上，问题是寻找 - 从A的最短路径，以在图B中。我认为BFS和Dijkstra的算法在这里工作，时间复杂度是完全相同的（O（V + E）），因为它是一个未加权的图，所以我们不能利用优先级队列。所以，一个简单的队列可以解决这个问题。但是，他们都不能解决这个问题：找到它们之间的路径。

Bidrectrol应该是在这一点上更好的解决方案。

来源

2011-07-02 SecureFish

DFS将产生...有趣的结果。爱丽丝知道鲍勃。爱丽丝也知道卡罗尔，谁知道戴夫，谁知道夏娃，谁知道鲍勃。 DFS同样可能返回Alice-> Carol-> Dave-> Eve-> Bob，因为它是Alice-> Bob。 :) –

注：答案编辑。

任何方法可能最终会被很慢。如果您需要重复执行此操作，最好找到图形的连接组件，之后该任务变为微不足道的O（1）操作：如果两个人在同一个组件中，则它们已连接。

注意，找到连接组件的第一次可能是缓慢的，但保持作为新的边/节点被添加到图中他们更新快。

有几种找到连接组件的方法。

一种方法是构造图的拉普拉斯，并期待在其本征值/本征矢量。零特征值的数量为您提供连接组件的数量。相应的特征向量的非零元素给出属于各个分量的节点。

另一种方式是大致如下：

创建节点的转换表。数组的元素n包含节点n转换为的节点的索引。
遍历图中的所有边缘(i,j)（表示i和j之间的连接）：
- 计算递归哪个节点做i和j变换以基于所述当前表中。让我们用k和l来表示结果。更新条目k，使其转变为l。更新条目i和j也指向l。
遍历再次表，并更新每个条目指向直接到它递归变换到的节点。

现在在同一个连接组件节点将在转换表相同的条目。因此，要检查两个节点是否连接，只需检查它们是否转换为相同的值。

每次将新节点或边添加到图中时，都需要更新转换表，但此更新将比原始表的计算快得多。

来源

2011-07-02 17:22:21 Szabolcs

简单地找到两个指定节点之间的最短路径是不是有点太多？ – biziclop

检查2个节点之间的连接与找到图的连通组件很少有共同之处。 – kilotaras

@biziclop，不，它取决于你已有的工具。 – Szabolcs

要找到两者之间的路径，您应该首先进行广度优先搜索。首先找到A的所有邻居，然后找到所有邻居的所有邻居A等。一旦B被击中，不仅你有从A到B的路径，但你也有一个这样的路径最短的。

Dijkstra's algorithm rocks，你也许可以通过从两端开始工作，即找到A的邻居和B的邻居并加以比较，从而加快速度。

如果您先进行深度优先搜索，那么您一次只搜索一条路径。这将会慢得多。

来源

2011-07-02 17:29:11 PengOne

DFS和BFS都具有O（N + M）复杂性，所以这不是很大的差别。 – kilotaras

DFS的平均时间差得多。这真的是平衡时间和空间的问题。 – PengOne

由于大多数路径都非常短，所以在实际社交网络中工作是一个好主意。这也是一些在某些系统中实际使用的想法。 – biziclop

我认为真正的标准是：A和B之间至少有N条路径短于K，或者A和B是直接连接的。我会选择K = 3和N接近5，即有5个共同的朋友。

来源

2011-07-02 17:30:55 kilotaras

你能解释为什么这会得到-1吗？根据[六度分离理论]（http://en.wikipedia.org/wiki/Six_degrees_of_separation），无论如何两个人将被连接。问题是他们连接不够。 – kilotaras

啊！我正在寻找这个，但找不到它。它是一个很好的理论，可以用于启发式算法，但是强加边界对于这个问题不会有好处。此外，N可以是零，这意味着它们没有连接。 +1为创意:)。 –

一种方法是使用联盟查找，加入所有链接union(from,to)，如果find(A) is find(B)为真，则A和B连接。这样可以避免递归搜索，但实际上会计算所有对的连接，并且不会为您提供连接A和B的路径。

来源

2011-07-02 17:32:14

如果您使用dfs来查找两个人是否连接到社交网络，那么这将需要很长时间！

你已经知道这两个人了，所以你应该使用Bidirectional Search.。但是，简单的双向搜索对于像社交网站那样大的图表来说是不够的。你将不得不使用一些启发式。维基百科页面有一些链接。 “A *使用最佳优先搜索并找到从给定初始节点到一个目标节点（超出一个或多个可能目标）的最低成本路径。 “

编辑：我建议A *因为“执行双向搜索的额外复杂性意味着如果我们有合理的启发式，A *搜索算法通常是更好的选择。所以，如果你不能形成合理的启发式，那么使用双向搜索。（形成一个很好的启发是不容易的）。）

来源

2011-07-02 17:36:19

我怀疑你可以用A *来公平。如果你有一个永不超调的启发式，A *才有效。你如何构建社交网络的这种启发式？ – biziclop

@biziclop：wiki：“执行双向搜索的额外复杂性意味着如果我们有合理的启发式算法，A *搜索算法通常是更好的选择。”如果你不能形成一个合理的启发式，然后使用双向搜索！ –

对于A *来说合理是不够的，正如我所说的，启发式必须是可接受的。我看不出有什么办法可以为这个问题制定任何不重要的可接受的启发式方法。 – biziclop

如何判断两个人是否连接

回答

相关问题