Блог

У меня есть матрица MATLAB, как показано ниже:

 column no:        1 2 3 4 5 6
matrix elements   1 1 2 3 6 2
  

Номера столбцов представляют идентификатор узла, а элементы матрицы представляют узел, на который указывает этот узел. Пожалуйста, помогите мне найти количество переходов от определенного узла к узлу 1. Я написал следующий код, но это не решает проблему.

 x = ones(1, n);
checkbit = zeros(1, n);
nodedest = [1 1 2 3 6 2];
hopcount = zeros(1, n);

for i = 1:n
    for j = 1:n
        if nodedest(j) == 1 amp;amp; checkbit(j) == 0
            hopcount(j) = hopcount(j)   1;
            checkbit(j) = 1;
        else
            x(j) = nodedest(j);
        end
        if x(j) ~= 1
            hopcount(j) = hopcount(j)   1;
            x(j) = nodedest(x(j));
        end
    end
end
  

Вы ищете поиск по ширине, чтобы найти кратчайший путь на вашем графике. Не касаясь данных каким-либо образом, вы можете сделать это за O (n) раз на узел, учитывая древовидную структуру вашего графика:

 nodedest = [1 1 2 3 6 2];
hopcount = zeros(1, 6);
for n = 2:6
    k = n
    while k ~= 1
        hopcount(n) = hopcount(n)   1
        k = nodedest(k)
    end
end
  

Если вы готовы изменить смысл ваших ребер (введя отношение «один ко многим»), вы могли бы выполнить то же самое за один проход, сократив сложность всего алгоритма с O (n²) до O (n) по времени. Компромисс будет заключаться в том, что сложность памяти увеличится с O (1) до O (n):

 nodedest = [1 1 2 3 6 2];

% Reverse the input
nodesource = cell(1, 6);
nodesource(:) = {[]}
for n = 2:6
    k = nodedest(n);
    nodesource{k} = [nodesource{k} n];
end

% implement bfs, using the assumption that the graph is a simple tree
hopcount = zeros(1, 6);
cache = [1];
hops = 0;
while ~isempty(cache)
    next = []
    for c = cache
        hopcount(c) = hops;
        next = [next nodesource(c)]
    end
    hops = hops   1;
    cache = next
end