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

mytomorrow

无向图的存储方式有邻接矩阵，邻接链表，稀疏矩阵等。无向图主要包含两方面内容，图的遍历和寻找联通分量。

0 j/ G4 Y: u0 }! {一、无向图的遍历
" \( r, E! s2 o' G无向图的遍历有两种方式—广度优先搜索(BFS)和深度优先搜索(DFS)。广度优先搜索在遍历一个顶点的所有节点时，先把当前节点所有相邻节点遍历了，然后遍历当前节点第一个相邻的节点的所有相邻节点，广度优先搜索使用队列来实现。深度优先搜索在遍历当前节点的所有相邻节点时，先对当前节点的第一个相邻节点进行访问，然后遍历第一个相邻节点的相邻节点，依次递归，因此深度优先搜索使用栈实现。
8 ]7 X8 k: V3 O# @0 {3 U- s  K
1、BFS图遍历代码：
% D6 e' @- Z8 P. M% \1 R4 Q& W6 E  i

• 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
  ( w! n6 h8 g% ~5 @

7 e) w5 X3 f/ S
6 l1 H# v  G8 D2 v; M! Z. C% A
2、DFS图遍历代码

游客，如果您要查看本帖隐藏内容请回复

( R3 h! v) [: b+ E, e, K3 t8 z* N
7 W( U! E( r) d( w4 `; \2 g4 h

yxlk

谢谢分享