#matlab
#matlab
Вопрос:
У меня есть матрица 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
Комментарии:
1. Можете ли вы привести пример, разработанный вручную?
2. @MadPhysicist Спасибо за ответ. Я обновил свой пост, пожалуйста, проверьте его.
3. Вы ищете breath-first поиск
Ответ №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 (n2) до 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