matlab练习程序(广度优先搜索BFS、深度优先搜索DFS)

如此经典的算法竟一直没有单独的实现过,真是遗憾啊。

广度优先搜索在过去实现的二值图像连通区域标记prim最小生成树算法时已经无意识的用到了,深度优先搜索倒是没用过。

这次单独的将两个算法实现出来,因为算法本身和图像没什么关系,所以更纯粹些。

广度优先搜索是从某一节点开始,搜索与其线连接的所有节点,按照广度方向像外扩展,直到不重复遍历所有节点。

深度优先搜索是从某一节点开始,沿着其搜索到的第一个节点不断深入下去,当无法再深入的时候,回溯节点,然后再在回溯中的某一节点开始沿另一个方向深度搜索,直到不重复的遍历所有节点。

广度优先搜索用的是队列作为临时节点存放处;深度优先搜索可以递归实现(算法导论就是用递归实现的伪代码),不过我这里是用栈作为临时节点存放处。

感觉也没什么好介绍的了,抄算法导论上的介绍也没什么意思,所有的内容都是书上的,真正学东西还是要看书。

下面是运行结果:

原连通图:

matlab练习程序(广度优先搜索BFS、深度优先搜索DFS)

广度优先搜索:

matlab练习程序(广度优先搜索BFS、深度优先搜索DFS)

深度优先搜索:

matlab练习程序(广度优先搜索BFS、深度优先搜索DFS)

matlab代码如下,其中的画图函数netplot.m

BFS.m

clear all;close all;clc
%初始化邻接压缩表
b=[ ; ; ; ;
; ; ; ]; m=max(b(:)); %压缩表中最大值就是邻接矩阵的宽与高
A=compresstable2matrix(b); %从邻接压缩表构造图的矩阵表示
netplot(A,) %形象表示 head=; %队列头
tail=; %队列尾,开始队列为空,tail==head
queue(head)=; %向头中加入图第一个节点
head=head+; %队列扩展 flag=; %标记某个节点是否访问过了
re=[]; %最终结果
while tail~=head %判断队列是否为空
i=queue(tail); %取队尾节点
for j=:m
if A(i,j)== && isempty(find(flag==j,)) %如果节点相连并且没有访问过
queue(head)=j; %新节点入列
head=head+; %扩展队列
flag=[flag j]; %对新节点进行标记
re=[re;i j]; %将边存入结果
end
end
tail=tail+;
end A=compresstable2matrix(re);
figure;
netplot(A,)

DFS.m

clear all;close all;clc
%初始化邻接压缩表
b=[ ; ; ; ;
; ; ; ]; m=max(b(:)); %压缩表中最大值就是邻接矩阵的宽与高
A=compresstable2matrix(b); %从邻接压缩表构造图的矩阵表示
netplot(A,) %形象表示 top=; %堆栈顶
stack(top)=; %将第一个节点入栈 flag=; %标记某个节点是否访问过了
re=[]; %最终结果
while top~= %判断堆栈是否为空
pre_len=length(stack); %搜寻下一个节点前的堆栈长度
i=stack(top); %取堆栈顶节点
for j=:m
if A(i,j)== && isempty(find(flag==j,)) %如果节点相连并且没有访问过
top=top+; %扩展堆栈
stack(top)=j; %新节点入栈
flag=[flag j]; %对新节点进行标记
re=[re;i j]; %将边存入结果
break;
end
end
if length(stack)==pre_len %如果堆栈长度没有增加,则节点开始出栈
stack(top)=[];
top=top-;
end
end A=compresstable2matrix(re);
figure;
netplot(A,)

compresstable2matrix.m

function A=compresstable2matrix(b)
[n ~]=size(b);
m=max(b(:));
A=zeros(m,m); for i=:n
A(b(i,),b(i,))=;
A(b(i,),b(i,))=;
end end
上一篇:Objective-C与C++的区别


下一篇:html5跨域通讯之postMessage的用法