algorithm - 如何在有向图中找到彼此距离 k 的所有节点(探索图中的每条边)？

Question

0

我正在解决一个问题，我需要找到彼此距离为 k 的所有节点。因此，如果 k=3，那么我需要找到它们通过距离 3 的路径连接的所有节点。没有自边，所以如果 i 有一条边指向 s，s 不能直接指向回 i。我想我在这里想到了两个实现，都涉及 BFS。我注意到 BFS 可能不会访问所有边缘的边缘情况，因为节点可能已经被访问过。

在每个节点做BFS。跟踪某个数组中每个节点的“级别”，其中 distance[0] 是根节点，distance1 是与根节点相邻的所有节点，distance[2] 是根节点的所有孙节点等在。然后为了找到距离 k 处的所有节点，我们查看 distance[i] 和 distance[i+k]。

做一次BFS，使用与上面相同的距离算法，但不要在每个节点都做BFS。反转所有边并再次执行 BFS 以查找任何遗漏的路径。这将比方法 1 具有更好的时间复杂度，但我不确定它是否真的会探索每条边和路径(在我的测试用例中它似乎是)。

有更好的方法吗？作为此图中 k = 2 的示例:

路径为 1 到 3、1 到 5、2 到 6、2 到 5、4 到 3、1 到 4。

编辑:边的反转不起作用，我目前最好的选择是先做一个 BFS，然后在每个节点做一个 DFS，直到达到深度 k。

Answer 1

您可以考虑一个基本的相邻矩阵 M，其中的元素不是 0 或 1 以指示连接，而是它们保存大小为 k 的可用路径。

例如对于 2->5，您将存储 M(2,5) = {1,2}(因为在节点 2 和 5 之间存在长度为 1 和长度为 2 的路径)

让 a 和 b 是 M 的两个元素

a * b 定义为:

ab_res = {} //a set without duplicates
for all size i in a
    for all size j in b
        s = i+j
        append(s) to ab_res
ab_res;

a + b 定义为:

ab_res = {}
for all size i in a
    append(i) to ab_res
for all size j in a
    append(j) to ab_res

这种方法不允许重新计算劣质路径。它也适用于循环。

下面是一个未优化的版本来说明算法。

const pathk = 2;
let G = {
    1:[2],
    2:[3,4,5],
    4:[6],
    6:[3]
}
//init M
let M = Array(6).fill(0).map(x=>Array(6).fill(0).map(y=>new Set));
Object.keys(G).forEach(m=>{
    G[m].forEach(to=>{
        M[m-1][to-1] = new Set([1]);
    })
});


function add(sums){
    let arr = sums.flatMap(s=>[...s]);
    return new Set(arr);
}
function times(a,b){
    let s = new Set;
    [...a].forEach(i=>{
        [...b].forEach(j=>{
            s.add(i+j);
        })
    });
    return s;
}
function prod(a,b, pathk){
    //the GOOD OL ugly matrix product :)
    const n = a.length;
    let M = Array(6).fill(0).map(x=>Array(6).fill(0).map(y=>new Set));
    a.forEach((row,i)=>{
        for(let bcol = 0; bcol<n; ++bcol){

            let sum = [];
            for(let k = 0; k<n; ++k){
                sum.push( times(a[i][k], b[k][bcol]) );
            }
            M[i][bcol] = add(sum);
            if(M[i][bcol].has(pathk)){
                console.log('got it ', i+1, bcol+1);
            }
        }
    })
    return M;
}

//note that
//1. you can do exponentiation to fasten stuff
//2. you can discard elems in the set if they equal k (or more...)
//3. you may consider operating the product on an adjency list to save computation time & memory..
let Mi = M.map(r=>r.map(x=>new Set([...x])));//copy
for(let i = 1; i<=pathk; ++i){
    Mi = prod(Mi,M, pathk);
}