广度优先搜索算法及其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;elset2 = floor( a1(i)/t );endif isempty( intersect(d,t2) )  % 是否已标号d = union(d,t2);           % 返回关联点数组endendd1 = setdiff(d,S1);     % 返回与已标号顶点相关联且未被标号的顶点集合%%%%% 对找到的顶点集合进行标号 %%%%%if isempty(d1)break;elseW(d1) = l+1;        % 对找到的顶点进行标号G1 = G(S1,:);G(a1) = 2;G(S1,:) = G1;G(:,S1) = G1';S1 = union(S1,d1);  % 更新已标号数组l = l+1;            % 更新标号数end
end