找回密码
 注册
关于网站域名变更的通知
查看: 1201|回复: 1
打印 上一主题 下一主题

无向图的遍历(BFS+DFS,MATLAB)算法导论

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2019-9-20 09:00 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

EDA365欢迎您登录!

您需要 登录 才可以下载或查看,没有帐号?注册

x
无向图的存储方式有邻接矩阵,邻接链表,稀疏矩阵等。无向图主要包含两方面内容,图的遍历和寻找联通分量。/ ^" y; h! \1 y) B" z6 O& F
/ z6 n/ W- s+ R; y9 x( P% {
一、无向图的遍历

" |. ~8 a8 j1 i  N7 r无向图的遍历有两种方式—广度优先搜索(BFS)和深度优先搜索(DFS)。广度优先搜索在遍历一个顶点的所有节点时,先把当前节点所有相邻节点遍历了,然后遍历当前节点第一个相邻的节点的所有相邻节点,广度优先搜索使用队列来实现。深度优先搜索在遍历当前节点的所有相邻节点时,先对当前节点的第一个相邻节点进行访问,然后遍历第一个相邻节点的相邻节点,依次递归,因此深度优先搜索使用栈实现。+ r; l  U& k  X! m2 B, j

  q4 A4 I6 C* N3 j0 p$ K) }1、BFS图遍历代码:2 `' |& d7 d. t- |
8 A/ Q: C) f% A
  • function result=BFSTraversal(startNode,Graph)
  • % 广度优先搜索
  • % Graph 图连通矩阵
  • [m n]=size(Graph);
  • nodelist=zeros(m,1);
  • queue=startNode;
  • nodelist(startNode)=1;
  • result=startNode;
  • while isempty(queue)==false
  •     i=queue(1);
  •     queue(1)=[];
  •     for j=1:n
  •         if(Graph(i,j)>0&&nodelist(j)==0&&i~=j)
  •             queue=[queue;j];
  •             nodelist(j)=1;
  •             result=[result;j];
  •         end
  •     end
  • end
    7 |) G% U; \0 ~( n

. E' o1 O. e) K" l: b' O6 z

% [2 n9 E+ w8 c0 W% [2 c: j4 F* b- z4 f1 W# l/ E3 w+ p
2、DFS图遍历代码
游客,如果您要查看本帖隐藏内容请回复
4 k2 G; h4 F- k  u7 g/ @- b3 E: n2 g" Q
6 a8 o) A! O3 S8 c' d5 d* v

3 V% i$ A2 X9 z+ D; F  B
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

推荐内容上一条 /1 下一条

EDA365公众号

关于我们|手机版|EDA365电子论坛网 ( 粤ICP备18020198号-1 )

GMT+8, 2025-10-29 10:21 , Processed in 0.156250 second(s), 24 queries , Gzip On.

深圳市墨知创新科技有限公司

地址:深圳市南山区科技生态园2栋A座805 电话:19926409050

快速回复 返回顶部 返回列表