matlab练习程序（广度优先搜索BFS、深度优先搜索DFS）

绝地灬酷狼 2022-03-29 05:20 382阅读 0赞

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

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

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

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

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

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

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

下面是运行结果：

原连通图：

![05201640-596964a279744fc9b5e5870686eead84.jpg][]

广度优先搜索：

![05201906-a95afcc076e54e2aba5ead72f6256728.jpg][]

深度优先搜索：

![05201946-8155d3c61e67461389d35d9d22b37f56.jpg][]

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

[Link 1]: http://www.cnblogs.com/tiandsp/archive/2012/12/06/2805276.html
[prim]: http://www.cnblogs.com/tiandsp/archive/2013/04/10/3012181.html
[05201640-596964a279744fc9b5e5870686eead84.jpg]: /images/20220329/d6124210e7724cb68449fdb33840fa36.png
[05201906-a95afcc076e54e2aba5ead72f6256728.jpg]: /images/20220329/ddfa21e4d8544b0096a3e6a11b3e8efb.png
[05201946-8155d3c61e67461389d35d9d22b37f56.jpg]: /images/20220329/62d7fab037334874bf35f17bad387897.png
[netplot.m]: http://www.cnblogs.com/tiandsp/archive/2012/12/26/2834654.html