Как найти все узлы на расстоянии k друг от друга в ориентированном графе (исследуя каждое ребро графа)?

Question

0

Я работаю над проблемой, где мне нужно найти все узлы на расстоянии k друг от друга. Поэтому, если k = 3, то мне нужно найти все узлы, где они соединены путем расстояния 3. Нет собственных ребер, поэтому, если у меня есть ребро, указывающее на s, s не может указывать обратно на i напрямую. Я думаю, что я подумал о двух реализациях здесь, оба с участием BFS. Я заметил крайний случай, когда BFS может не посещать все ребра, потому что узлы уже могут быть посещены.

Делать BFS на каждом узле. Отслеживайте «уровень» каждого узла в некотором массиве, где расстояние [0] является корневым узлом, расстояние1 - это все узлы, смежные с корневым узлом, расстояние [2] - все узлы, которые являются внуками корневого узла и т. Д. на. Затем, чтобы найти все узлы на расстоянии k, мы смотрим на расстояние [i] и расстояние [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.

* 1006. * например, для 2-> 5 вы должны хранить M(2,5) = {1,2} (потому что существует путь длины 1 и длины 2 между узлами 2 и 5)

let a и b два элемента M

a * b определяется как:

ab_res = {} //a set without dupplicates
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);
}