algorithm - Union-find 表示为社交网络

Question

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

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

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

但后来我想，这个社交网络怎么能用数据结构来表达。Union-find 是一种可以使用的数据结构。现在我必须明白所有成员都连接起来意味着什么。我如何查看实际的数据结构以及每个成员彼此成为朋友时的样子？

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

score 24 · Accepted Answer

当您向 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

score 23 · Accepted Answer

好的，为了解决这个练习，我假设日志文件看起来像这样：

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。

score 5 · Accepted Answer

为了查找是否所有成员都已连接，我使用了加权快速联合的概念。如果树的大小等于 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");

    }
}

score 1 · Accepted Answer

社交网络可以表示为树或图，其中每个节点都有 0 个n连接。

您需要的数据结构的主要部分是一个整数数组，其中每个元素索引可以解释为社交网络成员 ID，值是另一个成员的 ID，它是第一个成员的根。

您需要阅读日志并对union每个日志记录（构建树）在数据结构中执行操作并分析两个标准

每个成员都有一个连接 ( Set<Integer> haveConnection)
只有一个global根（因为从一开始你就会有很多没有连接的子网有自己的根）（Set<Integer> roots）

一旦满足这两个条件 - 您网络的所有成员都已连接。

祝你好运！

score 0 · Accepted Answer

安德烈斯提供的答案是正确的。还有另一种方式。您可以在此处使用与 N 个元素成比例的额外空间。因此，在合并两棵树后，您可以在树和联合函数中保留一个节点总数的数组，您必须将要合并的树中的节点数添加到作为根的树中的节点数两者的。所以添加后你只需要检查新树中的节点总数是否等于N。如果是，那么这将是所有N个成员都是彼此朋友的最早时间。

score 0 · Accepted Answer

这可以通过添加连接组件的数量来轻松完成。将 N 个成员视为 N 个对象，将 M 个时间戳视为 M 个并集。那么“所有成员连接的最早时间”就是连接组件的数量等于1的时间。

score 0 · Accepted Answer

将我的意见添加到@Andrés Soto。我总体上同意他的回答，但我认为我们不需要 getComponent() 方法。

在 WeightedUnionFind 中，请记住，我们有一个数组size，我们需要比较两个组件的大小，以便我们可以确定哪个联合哪个。

    public class WeightedQuickUnionUF {
        private int[] parent;   // parent[i] = parent of i
        private int[] size;     // size[i] = number of elements in subtree rooted at i
        private int count;      // number of components

每次有效联合后，我们都会更新大小。所以我们只需要判断更新后的大小是否等于N。如果是，这一步就是所有人都连通的步骤。

score 0 · Accepted Answer

Andres Soto 和 Monil 的两个答案在这里看起来都非常有效。

我想指出的一件事是，它看起来像是Kruskal 算法——即，找到无向边加权图的最小生成树/森林 (MST)。基本上，有成员（图的顶点）和时间戳（顶点之间的加权边） - 所谓的连通图。由于您获得了一个排序列表，因此该算法非常适合 - 您使用加权快速联合（即使使用路径压缩）并跟踪每棵树的大小以识别 MST（检查 Monil 答案）。

注意：如果图是断开的，那么最小生成树由每个组件/树的最小生成树组成。

UPD：注意到本杰明在问题下方的评论也提到了算法。

score 0 · Accepted Answer

数据来源：列数为num1、num2、date（用整数表示）。您可以将数据源保存为connections.txt以供程序使用：

10 是这个并集查找数据结构的节点总数。

使用以下代码运行程序：java-algs4 Ex1 < connections.txt

public class Ex1 {
    public static void main(String[] args) {
        int n = StdIn.readInt();
        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n);
        while (uf.count() > 1 && !StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.find(p) == uf.find(q)) continue;
            uf.union(p, q);
            int time = StdIn.readInt();
            StdOut.println(p + " " + q + " " + time);
        }
        StdOut.println(uf.count());
    }
}

score -1 · Accepted Answer

添加到@Andrés 的答案。这是检查所有连接与否的方法，将添加到 WeightedQuickUnionFind 类中。

public boolean isAllConnected(){
    int N = id.length;
    while(--N>0 && id[N] == id[0]);
    return N == 0;
}

algorithm - Union-find 表示为社交网络

10 回答 10

Related

Reference