|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
无向图的存储方式有邻接矩阵，邻接链表，稀疏矩阵等。无向图主要包含两方面内容，图的遍历和寻找联通分量。
' I0 q7 C7 H6 ~+ K1 ?' ~
$ z* y z: o9 {0 r& o* i一、无向图的遍历 `7 V5 A- |( l" H: s/ Z
无向图的遍历有两种方式—广度优先搜索(BFS)和深度优先搜索(DFS)。广度优先搜索在遍历一个顶点的所有节点时，先把当前节点所有相邻节点遍历了，然后遍历当前节点第一个相邻的节点的所有相邻节点，广度优先搜索使用队列来实现。深度优先搜索在遍历当前节点的所有相邻节点时，先对当前节点的第一个相邻节点进行访问，然后遍历第一个相邻节点的相邻节点，依次递归，因此深度优先搜索使用栈实现。9 C4 o( N0 Z& S
" R5 X+ F, ]& h4 B& I( C2 X6 s
1、BFS图遍历代码：1 o9 S( ?' u$ w2 o
) i+ V% ^2 l, V' B" y5 T3 B
- 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+ O* Z/ H7 u, {" z7 T
6 Y1 x. n+ s! U( J* d
4 z4 V# u _" _9 ]& Q0 z/ ?+ I
2、DFS图遍历代码' |! l# F; v8 ^8 T$ b. E6 }
3 \" V/ B h& m9 \$ ~+ l( K% n1 E1 E
|
|
/1 
发表于 2019-9-20 09:00
收藏
淘帖
支持！
反对！