广度优先搜索算法及其matlab程序详解

 #################本文为学习《图论算法及其MATLAB实现》的学习笔记#################

算法用途

广度优先搜索算法的应用

算法思想

广度优先搜索算法的步骤:

①,标号,令。
②当所有标号为  的、与顶点  相关联的边的端点都已标号时,则停止;否则,把与  相关联的边的未标号的顶点标以,并记录这些边,令,转②。

根据广度优先搜索算法思想,不难得出定理4.18,并且根据该定理,不难得出,用BFS算法不仅可以判定图的连通性,而且还可以找出连通图的一棵生成树。

定理4.18若BFS终止时仍有未标号的顶点,则G不连通:否则,由记录下的边导出的子图是G的一棵生成树。

 程序参数说明

 G: 邻接矩阵
W: 图顶点的标号

算法程序详解

%广度优先搜索算法
function [ W ] = BFSf1( G )
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% 输入：     G: 邻接矩阵
%%%%%%%%% 输出：     W: 图顶点的标号
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

n = size(G,1);      % 计算顶点树
W = zeros(1,n);     % 构建标号数组
l = 0;
v = 1;
a1 = find(G(v,:) == 1);  % 寻找与第一个顶点相关联的顶点
G(v,a1) = 2;        % 对其关联边标号为2
G(a1,v) = 2;
W(a1) = l+1;        % 更新标号数组
S1 = union(a1,v);   % S1 为已标号的顶点
l = l+1;

while ~isempty(G == 1)
    %%%%%%% 寻找与已经标号的顶点相关联且未被标号的顶点集合 %%%%%%
    a1 = find( G(S1,:) == 1 );  % 返回图中已标号的顶点与其他点有关联边的索引值
    t = length(S1);             % 计算已标号的顶点数
    d = [];
    
    %%%%% 寻找与已经标号的顶点相关联的顶点 %%%%%
    for i = 1:length(a1)
        if a1(i)/t > floor( a1(i)/t )
            t2 = floor( a1(i)/t )+1;
        else
            t2 = floor( a1(i)/t );
        end
        if isempty( intersect(d,t2) )  % 是否已标号
            d = union(d,t2);           % 返回关联点数组
        end
    end
    d1 = setdiff(d,S1);     % 返回与已标号顶点相关联且未被标号的顶点集合
    
    %%%%% 对找到的顶点集合进行标号 %%%%%
    if isempty(d1)
        break;
    else
        W(d1) = l+1;        % 对找到的顶点进行标号
        G1 = G(S1,:);
        G(a1) = 2;
        G(S1,:) = G1;
        G(:,S1) = G1';
        S1 = union(S1,d1);  % 更新已标号数组
        l = l+1;            % 更新标号数
    end
end