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

2014年1月12日 09:52
转载(0) / 评论(0) / 浏览(778)

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

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

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

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

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

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

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

下面是运行结果:

原连通图:

\

广度优先搜索:

\

深度优先搜索:

\

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

BFS.m

复制代码
clear all;close all;clc
%初始化邻接压缩表
b=[1 2;1 3;1 4;2 4; 2 5;3 6;4 6;4 7];

m=max(b(:));                %压缩表中最大值就是邻接矩阵的宽与高
A=compresstable2matrix(b);  %从邻接压缩表构造图的矩阵表示
netplot(A,1)                %形象表示

head=1;             %队列头
tail=1;             %队列尾,开始队列为空,tail==head
queue(head)=1;      %向头中加入图第一个节点
head=head+1;        %队列扩展

flag=1;             %标记某个节点是否访问过了
re=[];              %最终结果 while tail~=head    %判断队列是否为空
    i=queue(tail);  %取队尾节点 for j=1:m if A(i,j)==1 && isempty(find(flag==j,1))    %如果节点相连并且没有访问过
            queue(head)=j;                          %新节点入列
            head=head+1;                            %扩展队列
            flag=[flag j];                          %对新节点进行标记
            re=[re;i j];                            %将边存入结果 end end tail=tail+1; end A=compresstable2matrix(re);
figure;
netplot(A,1)
复制代码

DFS.m

复制代码
clear all;close all;clc
%初始化邻接压缩表
b=[1 2;1 3;1 4;2 4; 2 5;3 6;4 6;4 7];

m=max(b(:));                %压缩表中最大值就是邻接矩阵的宽与高
A=compresstable2matrix(b);  %从邻接压缩表构造图的矩阵表示
netplot(A,1)                %形象表示

top=1;                  %堆栈顶
stack(top)=1;           %将第一个节点入栈

flag=1;                 %标记某个节点是否访问过了
re=[];                  %最终结果 while top~=0 %判断堆栈是否为空
    pre_len=length(stack);    %搜寻下一个节点前的堆栈长度
    i=stack(top);             %取堆栈顶节点 for j=1:m if A(i,j)==1 && isempty(find(flag==j,1))    %如果节点相连并且没有访问过 
            top=top+1;                          %扩展堆栈
            stack(top)=j;                       %新节点入栈
            flag=[flag j];                      %对新节点进行标记
            re=[re;i j];                        %将边存入结果 break; end end if length(stack)==pre_len   %如果堆栈长度没有增加,则节点开始出栈
        stack(top)=[];
        top=top-1; end end A=compresstable2matrix(re);
figure;
netplot(A,1)
复制代码

compresstable2matrix.m

复制代码
function A=compresstable2matrix(b)
    [n ~]=size(b);
    m=max(b(:));
    A=zeros(m,m); for i=1:n
        A(b(i,1),b(i,2))=1;
        A(b(i,2),b(i,1))=1; end end
复制代码

评论(0)

发表评论
登录
我可以
  • 评论
关联标签
Matlab × 12
关联热门电子辑
类似的技文

浏览(978) / 评论(0) / 2014年1月12日 09:50

浏览(795) / 评论(0) / 2014年1月12日 09:55

浏览(0) / 评论(0) / 2014年1月9日 22:23

浏览(938) / 评论(0) / 2014年1月10日 10:57

浏览(612) / 评论(0) / 2014年1月12日 10:05

浏览(929) / 评论(0) / 2014年1月12日 10:07

浏览(789) / 评论(0) / 2013年9月30日 22:27

浏览(772) / 评论(0) / 2014年1月12日 10:09

浏览(503) / 评论(0) / 2013年9月30日 22:27

浏览(838) / 评论(0) / 2014年1月13日 09:11