algorithm - 如何从用户的联系人中找到 "possible friends"

Question

假设我有一些用户的联系人(如手机中的联系人)。在联系人中，用户将有他们 friend 的联系信息(如电话号码)。不大，我们可以假设它少于 1000。

如果在A的联系人中，A有B的联系方式，我们说A和B是 friend (即使B没有A)。

现在，我们考虑如果 User1 和 User2 有两个以上的共同 friend User3 和 User4 或更多，我们说 User1 和 User2 是可能的 friend (如果 User1 和 User2 不是 friend )。

我们有 n 个用户的联系人。如何找到所有这些用户的可能 friend 。

谢谢!

Answer 1

怎么样:获取 UserA 和 UserB 之间可能的路径数，然后如果数字>2，则 userA 和 userB 可能是 friend 。

首先，您需要创建图形的邻接矩阵 (http://en.wikipedia.org/wiki/Adjacency_matrix)

类似的东西:

//Numbers of edges
int n = 5;

int[][] adjacencymatrix = new int[][] {
    new int[] {1,1,1,0,0}, //    1
    new int[] {1,1,1,1,0}, //  / | \
    new int[] {1,1,1,1,0}, // 0  |  3 - 4
    new int[] {0,1,1,1,1}, //  \ | /
    new int[] {0,0,0,1,1}, //    2
};

然后，还有一些东西

// stock the path
int[] path = new int[n];

// lock for the search (all at false at the beginning)
boolean[] taboo = new boolean[n];

// start and stop edges
int source=0;
int target=4;

最后:

void explore(int position, int depth) {
    path[depth]=position;

    // arrived at stop point -> finished
    if (position==target) {
        // print the solution
        for(int i=0;i<=depth;i++) System.out.print(path[i]+" ");
        System.out.print("\n");
        return;
    }

    taboo[position]=true; // remember you already went on this edge

    // explore remaining paths
    for(int i=0;i<n;i++) {
        if (adjacencymatrix[position][i]==0 || taboo[i]) continue;
        explore(i,depth+1);
    }

    taboo[position]=false;
}

基本上它所做的是找到从 UserA 到 UserB 的所有唯一路径。希望对您有所帮助!