[解決済み] グラフ理論 Matlab BFSアルゴリズム

質問内容

隣接行列をBFSリストに変換する関数を書こうとしています。出力は2つの行を含み、1つはノードのインデックス、もう1つはノードを訪れる順序です。 Aは隣接行列であり、関数は次のようになります。

function [ forest ] = Find_BFS_forest( A )

例えば 入力 A を [0,1,0,0,1,0;1,0,1,0,0,0;0,1,0,0,0,0;0,0,0,0,0;1,0,0,0,0,0;0,0,0,0,0] とするとき。 edge_list は {(1,2) (1,5) (2,3)} である。出力は [1,2,5,3,4,6;0,1,1,2,0,0] のようにしたい。

n=length(A);
% vis to mark if a node is visited earlier or not
vis=zeros(n,1);
% pred to predecessor of each node
pred=zeros(n,1);
% path to store the bfs traversal
path =zeros(n,1); pp = 1;

for i = 1:n
    % start bfs from each unvisited node i
    if vis(i) == 0
        % search queue and search queue tail/head
        sq=zeros(n,1);
        sqt=1;
        sqh=0;
        % push starting node in the queue
        sq(sqt)=i;
        while sqt-sqh>0
            % pop v off the head of the queue
            sqh=sqh+1;
            v=sq(sqh);
            path(pp) = v;
            pp=pp+1;
            for u=1:n
                if A(v,u)==1 && vis(u)==0
                    % if u is connected to v and is unvisited push it to the queue
                    sqt=sqt+1;
                    sq(sqt)=u;
                    vis(u) = 1;
                    pred(u)= v;
                end
            end
        end
    end
end
% create the output forest
forest = zeros(2,n);
for i=1:n
    forest(1,i) = path(i);
    forest(2,i) = pred(path(i));
end
end

これは私が今持っているコードですが、ノードが繰り返されています。どこを変更すればいいのでしょうか？

ありがとうございました。

どのように解決するのですか？

各ツリーの初期ノードを visited :

for i = 1:n
    % start bfs from each unvisited node i
    if vis(i) == 0
        vis(i) = 1;   % mark initial node as visited <-- added
        % search queue and search queue tail/head
...

追加後の出力。

forest =
   1   2   5   3   4   6
   0   1   1   2   0   0