联盟发现表达为社交网络

Question

这是我想回答的面试问题:

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

我想的第一件事就是......"我不能这样做!".

但后来我想到这个社交网络怎么能表达为数据结构.Union-find是一种可以使用的数据结构.现在我必须了解所有成员连接时的含义.如何查看实际数据结构以及每个成员彼此成为朋友时的样子？

我想只有在我能够从视觉上或概念上理解系统如何完全连接之后我才能开始弄清楚如何找到与该事件相对应的时间戳.

Answer 1

向union-find数据结构添加友谊时,可以注意它是否会导致连接两个图形组件.只需继续添加边缘,直到发生这些合并事件的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

其中2个第一个数字是形成友谊的成员,其后是时间戳.

另一个需要注意的重要事项是,练习中提到文件已排序,因此我决定按升序对其进行排序.

有了这些信息,您可以使用类中提供的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

为了确定所有成员是否已连接，我使用了加权 Quick-union 的概念。如果树的大小等于 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");

    }
}