Union-find表示为社会网络

Question

这是我试图回答的一个面试问题：

给定一个包含N成员的社交网络和一个包含M时间戳的日志文件，在该文件中，成员对建立友谊，设计一种算法来确定所有成员连接的最早时间(即每个成员都是friend...of朋友的朋友)。假设日志文件是按时间戳排序的，而友谊是一种等价关系。算法的运行时间应该是M log N或更好，并使用与N成比例的额外空间。

我想的第一件事是.“我不能这么做！”

但后来我想，这个社会网络是如何用数据结构来表达的。Union-find是一种可以使用的数据结构。现在我要明白，当所有议员都有联系时，这是甚麽意思？当每个成员成为朋友时，我怎样才能看到实际的数据结构和它的样子呢？

我认为，只有在我能够从视觉或概念上理解系统是如何完全连接起来的时候，我才能开始思考如何找到与该事件相对应的时间戳。

Answer 1

当您将友谊添加到联合查找数据结构时，您可以注意如果它导致两个图组件被连接起来。只要继续添加边，直到这些合并事件中的N-1发生为止。

以伪码形式：

G := UnionFind(1..N)
count := 0
for timestamp, p1, p2 in friendships {
    if G.Find(p1) != G.Find(p2) {
        G.Union(p1, p2)
        count++
        if count == N-1 {
            return timestamp
        }
    }
}
return +infinity

Answer 2

为了解决这个问题，我假设日志文件将如下所示：

0 1 2015-08-14 18:00:00
1 9 2015-08-14 18:01:00
0 2 2015-08-14 18:02:00
0 3 2015-08-14 18:04:00
0 4 2015-08-14 18:06:00
0 5 2015-08-14 18:08:00
0 6 2015-08-14 18:10:00
0 7 2015-08-14 18:12:00
0 8 2015-08-14 18:14:00
1 2 2015-08-14 18:16:00
1 3 2015-08-14 18:18:00
1 4 2015-08-14 18:20:00
1 5 2015-08-14 18:22:00
2 1 2015-08-14 18:24:00
2 3 2015-08-14 18:26:00
2 4 2015-08-14 18:28:00
5 5 2015-08-14 18:30:00

其中，两个第一个号码是组成友谊的成员，然后是时间戳。

另一件重要的事情是，练习提到文件是排序的，所以我决定按升序排序。

有了这些信息，您就可以使用类中提供的WeightedQuickUnionFind数据结构，并且可以简单地处理对成员执行联合操作的文件，一旦您完成联合，您就可以询问结构中有多少组件，如果只有一个组件意味着所有成员都有等价关系。

下面是我做过的代码：

public static void main(String[] args) {

        int n = StdIn.readInt();
        WeightedQuickUnion uf = new WeightedQuickUnion(n);
        String date, time;
        //timestamps are sorted ascending
        while (!StdIn.isEmpty()) {

            int p = StdIn.readInt();
            int q = StdIn.readInt();
            date = StdIn.readString();
            time = StdIn.readString();


            uf.union(p, q);

            StdOut.println("["+p+","+q+"]");

            if(uf.getComponents() == 1){
                StdOut.println("All members were connected at: " + date + time);
                break;
            }

        }

性能将是M lg n，因为您正在迭代M次(日志文件中的行数)，并且联合操作需要: lg n。

Answer 3

为了找出是否所有的成员都是连接的，我使用了加权快速联合的概念。如果树的大小等于n，那么我们可以说所有的成员都是连通的。我的守则：

class MyClas {
    private int[] a;
    private int[] size;
    int N=0;
    public MyClas(int n){
        N=n;
        a = new int[n];
        size = new int[n];
        for(int i=0;i<n;i++){
            a[i]=i;
            size[i]=1;
        }
    }
    private int root(int x){
        while(x != a[x]){
            x=a[x];
        }
        return x;
    }
    public boolean connected(int p, int q){
        return root(p)==root(q);
    }
    public void union(int p,int q, String timestamp){
        int i = root(p);
        int j = root(q);
        if(i == j) return;
        if(size[i] < size[j]){
            a[i] = j;
            size[j]+=size[i];
            if(size[j]==N){
                System.out.println("All Members are connected at Timestamp"+ timestamp);
            }
        }
        else{
            a[j] = i;
            size[i]+=size[j];
            if(size[i]==N){
                System.out.println("All Members are connected at Timestamp"+ timestamp);
            }
        }
    }

}
public class MyClass {
    public static void main(String args[]) {
      MyClas obj = new MyClas(6);
      obj.union(1,5, "2019-08-14 18:00:00");
      obj.union(2,4, "2019-08-14 18:00:01");
      obj.union(1,3, "2019-08-14 18:00:02");
      obj.union(5,2, "2019-08-14 18:00:03");
      obj.union(0,3,"2019-08-14 18:00:04");
      obj.union(2,1,"2019-08-14 18:00:05");

    }
}