Как определить количество прыжков с помощью вектора?

Question

У меня есть матрица 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 && 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

Answer 1

Вы ищете поиск в ширину , чтобы найти кратчайший путь на вашем графике. Не касаясь данных каким-либо образом, вы можете сделать это за 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