如何在大图中找到所有连接的两条边？

Question

我有一个大图（例如，facebook网络，twitter网络），我想找到两个连接的边缘。例如，像社交网络中的p1 < ---> p2 < ---> p3，p1，p2，p3是三个不同的人，但它们是连接的。我知道有一些用于查找三角形的算法，但除了三角形之外，我还需要找到上述组件（即通过从三角形中删除一条边形成的组件）。顺便说一下，有没有这样一个组件的术语？

THanks。

Answer 1

我相信你正在寻找输入图形的connected components。基本上，这些可以通过使用depth-first search找到。你从图中的某个点开始。终止时，所有访问的节点形成一个连接组件。然后，通过选择下一个未访问的节点进行迭代，发现连接的组件直到访问所有节点。

Answer 2

使用depth first search并记录递归深度：一旦进入深度2，打印堆栈中的所有节点。

重复每个节点，根据需要消除重复。

我不知道一个特定的术语，你似乎想找到任何2个节点之间长度为2的所有路径。

Answer 3

原因是你没有发现很多关于这方面的出版物，这是一个太简单的问题。

如果您有对称关系，则节点“b”的任意两个邻居“a”和“c”形成这样的“1-传递”连接：b是链接。 map-reduce的伪代码是

def map(b, neighbors): 
    for a in neighbors: 
    for c in neighbors: 
     if not a == c: 
     send(a, c) 

如果关系不对称，只需添加另一个映射器使其对称即可。