#################本文为学习《图论算法及其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 == 1d = 0;
end
k(1) = 1;
j = 2;
l = 2;while d%%%%%%%% 步骤3 %%%%%%%%a = find( W(v,:) == 1 ); % 返回与父亲顶点相关联的顶点%%%%%%%% 步骤5 %%%%%%%%if isempty(a) & f(v) ~= 0W(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; % 更新边标号endendendb = sum(sum(W)); % 更新未标号的总边数c = sum(k == 0); % 更新未标号的顶点数if c == 0 & v == 1 % 若顶点均已标号，结束循环d = 0;end
end
W;
