|
EDA365欢迎您登录!
您需要 登录 才可以下载或查看,没有帐号?注册
x
无向图的存储方式有邻接矩阵,邻接链表,稀疏矩阵等。无向图主要包含两方面内容,图的遍历和寻找联通分量。6 _3 g2 E) g: j$ }' v3 v4 U
c F$ D/ T( }1 l# @一、无向图的遍历 ! J) n8 J1 X3 E5 i
无向图的遍历有两种方式—广度优先搜索(BFS)和深度优先搜索(DFS)。广度优先搜索在遍历一个顶点的所有节点时,先把当前节点所有相邻节点遍历了,然后遍历当前节点第一个相邻的节点的所有相邻节点,广度优先搜索使用队列来实现。深度优先搜索在遍历当前节点的所有相邻节点时,先对当前节点的第一个相邻节点进行访问,然后遍历第一个相邻节点的相邻节点,依次递归,因此深度优先搜索使用栈实现。
/ ?) Y W! k, u. [: F% u
/ P* _" i. J4 w6 n1、BFS图遍历代码:
1 ?( v& _* v' Z, \- u8 F6 ~6 V+ V3 m" D. P
- 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
Q7 P4 E3 _$ I, a1 x/ E $ V* j4 q a1 g& D
7 \" o7 F& }' S3 f) }% L, I
/ M. c9 t) [4 h
2、DFS图遍历代码
$ t2 G$ A9 m: P5 E% l& t
3 v3 }( N8 B ]5 C% \) t0 U7 V6 L7 t, Y. l3 c7 r, [( s" L
|
|