您现在的位置是:首页 > 正文

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

2024-02-01 01:34:59阅读 2

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

广度优先搜索在过去实现的二值图像连通区域标记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

 

转载于:https://www.cnblogs.com/tiandsp/p/3174262.html

网站文章

  • win10 安装配置Git

    win10 安装配置Git

    3.继续,执行ssh-keygen-trsa,(注意ssh-keygen无空格),生成SSH(你的电脑与Gitee通信的安全连接)百度地址链接https//pan.baidu.com/s/1Y_P_e...

    2024-02-01 01:34:43
  • 机器学习概述

    简介什么是机器学习?机器学习就是从【数据】中自动分析,获得【规律(模型)】,并利用规律对未知数进行【预测】。样本数据(数据集)的载体- 通常情况下历史数据都不会存储在数据库中,而是存储在文件中(.cs...

    2024-02-01 01:34:37
  • Mysql 基于GTID的主从复制及切换

    参考http://imysql.com/tag/gtidhttp://mysqllover.com/?p=594Mysql 基于GTID的主从复制及切换一、主从复制配置两个mysql服务的my.cnf 中相关内容配置[mysqld]#从复制数据库表设置replicate-wild-ignore-table = mysql.%,information_schema.%,inno...

    2024-02-01 01:34:02
  • linux上传文件put,详解Linux ftp 命令行中下载文件get与上传文件put的操作方法

    尽管现在有许多好的FTP应用程序,但服务器命令行ftp命令的应用程序仍然很多,下面就让电脑乐园小编带你一起来学习详解Linux ftp 命令行中下载文件get与上传文件put的操作方法。介绍:从本地以...

    2024-02-01 01:33:55
  • 切面条问题

    切面条问题

    切面条问题 python

    2024-02-01 01:33:27
  • Java架构师面试题——JVM性能调优

    JVM内存调优 对JVM内存的系统级的调优主要的目的是减少GC的频率和Full GC的次数。 1.Full GC 会对整个堆进行整理,包括Young、Tenured和Perm。Full GC因为需要对...

    2024-02-01 01:33:20
  • python中reversed函数怎么用_Python3 reversed 函数

    Python3reversed 函数描述Python3 reversed 函数返回一个反转的迭代器。语法以下是 reversed 的语法:reversed(seq)参数seq -- 要转换的序列,可以...

    2024-02-01 01:33:12
  • OpenGL之Shader编程入门

    OpenGL之Shader编程入门

    shader编程基本概念。

    2024-02-01 01:33:06
  • php 全局函数 加到类,全局PHP函数通过类链接

    是否可以通过对象/类链接所有PHP函数?我有这个想法,我想这样的事情:$c = new Chainer();$c->strtolower('StackOverFlow')->ucwords(/* the value from the first function argument */)->str_replace('St', 'B', /* the value from the ...

    2024-02-01 01:32:37
  • MyBatis-Plus乐观锁插件

    MyBatis-Plus乐观锁插件

    1、模拟修改冲突 1、创建一个数据库,添加一个数据 CREATE TABLE t_product( `id` BIGINT(20) not null COMMENT '主键ID', `...

    2024-02-01 01:32:28