当前位置：首页 > news >正文

海尔网站建设的优势wordpress爱搭配

news 2025/9/12 23:37:46

海尔网站建设的优势,wordpress爱搭配,如何提升关键词的自然排名,lamp网站建设#################本文为学习《图论算法及其MATLAB实现》的学习笔记################# 算法用途广度优先搜索算法的应用算法思想广度优先搜索算法的步骤: ①,标号,令。 ②当所有标号为的、与顶点相关联的边的端点都已标号时,则停止;否则,把与相关联的边的未标号的…

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

算法用途

广度优先搜索算法的应用

算法思想

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

① $\forall v\in V(G)$ ,标号 $l(v)=0$ ,令 $l=0$ 。
②当所有标号为 $l$ 的、与顶点 $u$ 相关联的边的端点都已标号时,则停止;否则,把与 $u$ 相关联的边的未标号的顶点标以 $l+1$ ,并记录这些边,令 $l=l+1$ ,转②。

根据广度优先搜索算法思想,不难得出定理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

查看全文

http://www.15wanjia.com/news/156117.html