深度优先搜索算法及其matlab程序详解
#################本文为学习《图论算法及其MATLAB实现》的学习笔记#################
深度优先搜索算法(DepthFirst Search),简记DFS算法,是图论中的首要算法,其思想方法渗透到图论中的许多算法之中,尤其是DFS算法在求生成树、割点、块和平面图嵌入算法中起着极为关键的作用。
算法用途
DFS算法的MATLAB实现
算法思想
①标记一切边“未用过”,对任意顶点。令。
②。
③若没有“未用过”的关联边,转⑤。
④ 选一条“未用过”的与关联的边,标记 “用过”。若,转③;否则转②。
⑤ 若 停止。
⑥ ,转③。
其中,上述中的k(v)称为顶点υ的DFS编码;f(u)称为顶点v的父,称为f(v)的子,且以 f(v)为始点、为终点的有向边称为父子边。
根据上述DFS算法,易知该算法的复杂度为,并得出定理4.19,由此可见,用DFS算法可以找出连通图的某固定顶点的外向生成树。
定理4.19设连通图G,则由DFS中产生的父子边导出的子图是以s为根的外向生成树,并日在返回边中,或a是b的祖先,或a是b的后代孙。
程序参数说明
G: 图的邻接矩阵
W: 图的边的访问顺序,按照顺序从小到大访问
k: 图的顶点标号
f: 相应顶点的父亲顶点
算法程序详解
%深度优先搜索算法
function [W, k, f] = DFS3(G)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% 输入: G: 图的邻接矩阵
%%%%%%%%% 输出: W: 图的边的访问顺序,按照顺序从小到大访问
%%%%%%%%% k: 图的顶点标号
%%%%%%%%% f: 相应顶点的父亲顶点
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
n = size(G,1); % 计算顶点数
W = G;
v = 1;
k = zeros(1,n); % 返回标号数组
f = zeros(1,n); % 返回相应顶点的父亲顶点数组
b = sum(sum(W == 1)); % 计算未标号的总边数
c = sum(k == 0); % 未标号的顶点数
d = 1;
if b == 0 & c == 0 & v == 1
d = 0;
end
k(1) = 1;
j = 2;
l = 2;
while d
%%%%%%%% 步骤3 %%%%%%%%
a = find( W(v,:) == 1 ); % 返回与父亲顶点相关联的顶点
%%%%%%%% 步骤5 %%%%%%%%
if isempty(a) & f(v) ~= 0
W(v,f(v)) = l; % 将用过的边进行标号
l = l + 1; % 更新边标号
v = f(v);
else
%%%%%%%% 步骤4 %%%%%%%%
for i = 1:length(a)
if k(a(i)) == 0 % 若顶点 a 未标号
k(a(i)) = j;
j = j + 1; % 更新顶点标号
W(v,a(i)) = l; % 将边标记为用过,并对其标号
l = l + 1; % 更新边标号
f(a(i)) = v; % 更新父亲数组标号
v = a(i); % 对父亲标号进行更新
break;
elseif k(a(i)) ~= 0 % 若顶点 a 已标号
W(v,a(i)) = l; % 将边标记为用过,并对其标号
l = l + 1; % 更新边标号
end
end
end
b = sum(sum(W)); % 更新未标号的总边数
c = sum(k == 0); % 更新未标号的顶点数
if c == 0 & v == 1 % 若顶点均已标号,结束循环
d = 0;
end
end
W;
原文地址:https://blog.csdn.net/weixin_72217561/article/details/142450364
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!