时间戳

首页 > 解决方案 > 图论 Matlab BFS 算法

matlab - 图论 Matlab BFS 算法

问题描述

我正在尝试编写一个将邻接矩阵转换为 BFS 列表的函数。输出包含两行，一是节点的索引，二是访问节点的顺序。该函数应如下所示，其中 A 是邻接矩阵：

函数 [ 森林 ] = Find_BFS_forest( 一 )

例如，当输入 A 为 [0,1,0,0,1,0;1,0,1,0,0,0;0,1,0,0,0,0;0,0,0 ,0,0,0;1,0,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

这是我现在拥有的代码，但节点正在重复。我应该在哪里进行更改？？

提前致谢！

标签： matlabgraph-theorybreadth-first-search

解决方案

您忘记将每棵树的初始节点标记为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

推荐阅读