java - 递归查找 "indirect relationships"

Question

所以我有二维 boolean 数组 a，它应该代表不同人之间的关系/友谊。每个人都通过他们的 id(数组索引)来识别，如果例如a[1][0] 为 true，则 1 和 0 是 friend 。如果 2 个人是 friend ，他们的“ friend 距离”就是 1。人们也可以通过其他人成为 friend ，例如:如果a[1][0] = true，a[2][0] = true，a[2][1] = false，则人员1和人员2不是直接 friend ，而是因为人员1是人员0的 friend ，而人 0 是人 2 的 friend ，人 1 和人 2 是距离为 2 的 friend 。现在我想递归地确定 2 个人是否是给定距离内的 friend ，或者是否不是。我已经写了这段代码:

public static boolean areFriends(int id0, int id1, int e) {
        if (e <= 0) {
            return false;
        }
        if (array[id0][id1]) {
            return true;
        }
        for (int i = 0; i < array.length; i++) {
            if (array[id0][i]){
                (areFriends(i, id1, --e);
            }
        }
        return false;
    }
}

代码至少应该做的是遍历 id0s friend 列表，并检查每个数组条目，如果 id0 和检查的人 idx 是 friend 。如果是，则重复该方法，用 idx 替换 id0s 位置，并 --e。因此，再次检查所有 idx 的关系，如果 idx 是另一个人的 friend ，则整个循环会重复，直到“ friend 距离”e 太高(因此不存在间接友谊)或找到间接友谊。 p>

但显然这段代码并没有完全做到这一点，所以我会对我做错了什么或如何修复错误的任何提示有所帮助。

Answer 1

最好将数据表示为图，然后使用 Dijikstra 算法来查找两个节点之间的路径。事实上，每个人都由一个节点表示，两个节点之间的弧调节了友谊关系。

对于您的数据模块，我建议作为解决方案:

public static boolean areFriends(boolean friends[][], int id1, int id2, int distance) {
    if (friends[id1][id2]) {
        return true;
    }

    if (distance == 0) {
        return freinds[id1][id2];
    }

    for (int i = 0; i < friends[id1].length; i++) {
        if (i != id1 && friends[id1][i] && areFriends(friends, i, id2, distance - 1)) {
            return true;
        }
    }

    return false;
}