EDA365电子论坛网
标题:
无向图的遍历(BFS+DFS，MATLAB)算法导论
[打印本页]
作者:
mytomorrow
时间:
2019-9-20 09:00
标题:
无向图的遍历(BFS+DFS，MATLAB)算法导论
无向图的存储方式有邻接矩阵，邻接链表，稀疏矩阵等。无向图主要包含两方面内容，图的遍历和寻找联通分量。
6 ]2 ]% F8 l# ]3 m6 T
& \1 b$ z* ^+ H- a4 O
一、无向图的遍历
+ o0 {& H: p: T8 D
无向图的遍历有两种方式—广度优先搜索(BFS)和深度优先搜索(DFS)。广度优先搜索在遍历一个顶点的所有节点时，先把当前节点所有相邻节点遍历了，然后遍历当前节点第一个相邻的节点的所有相邻节点，广度优先搜索使用队列来实现。深度优先搜索在遍历当前节点的所有相邻节点时，先对当前节点的第一个相邻节点进行访问，然后遍历第一个相邻节点的相邻节点，依次递归，因此深度优先搜索使用栈实现。
: X: F- q N7 y- @' V( c+ S1 r
$ g/ ~! L( V7 J0 s* c
1、BFS图遍历代码：
# n, f3 V$ i; T: K8 ^. P) d$ I
9 [$ ?" z2 E' e/ Y" r
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
/ e3 @' a/ ?" ]) x
, x! i0 ]0 Q* S' y
2 n. X4 e+ g1 g5 N
% T" o: S2 h9 ?) ~
2、DFS图遍历代码
, E# |* d3 @% E+ ~ V# G. [. M
+ g# _5 b, b! {+ {* a# l
- N% j1 h$ E) i9 a
作者:
yxlk
时间:
2019-9-20 17:42
谢谢分享
欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)
Powered by Discuz! X3.2