项城网站建设,绍兴市工程建设网站,专业网络营销外包,企业画册vi设计#################本文为学习《图论算法及其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) l1; % 更新标号数组
S1 union(a1,v); % S1 为已标号的顶点
l l1;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) l1; % 对找到的顶点进行标号G1 G(S1,:);G(a1) 2;G(S1,:) G1;G(:,S1) G1;S1 union(S1,d1); % 更新已标号数组l l1; % 更新标号数end
end
