|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
无向图的存储方式有邻接矩阵，邻接链表，稀疏矩阵等。无向图主要包含两方面内容，图的遍历和寻找联通分量。
6 q2 T% v3 C6 v5 S9 M7 o8 e A" O8 {( `) h- `
一、无向图的遍历 ' T$ J* q* V, Q9 i9 b
无向图的遍历有两种方式—广度优先搜索(BFS)和深度优先搜索(DFS)。广度优先搜索在遍历一个顶点的所有节点时，先把当前节点所有相邻节点遍历了，然后遍历当前节点第一个相邻的节点的所有相邻节点，广度优先搜索使用队列来实现。深度优先搜索在遍历当前节点的所有相邻节点时，先对当前节点的第一个相邻节点进行访问，然后遍历第一个相邻节点的相邻节点，依次递归，因此深度优先搜索使用栈实现。
D- r0 q* f1 e5 g8 k
9 ~7 O8 D S& O' N( R# Q8 w7 z1、BFS图遍历代码：
5 @- X7 D& R5 b* E6 ~4 `8 S1 U7 N
! i# L( B0 Y2 ]3 h- 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
. U( x9 i n* S/ j- p3 @9 |7 {2 C# v
& t9 f9 V; d% E
# y- t! t# ^( n! G. q
* U) v5 U$ _- u3 \8 m% c* f* G# N$ [2、DFS图遍历代码3 H4 R8 X# Y7 j8 \. i1 n
1 k. Q T. ]- O0 K) G2 V$ P9 t
0 Y" u% c& o5 k% Y
|
|
/1 
发表于 2019-9-20 09:00
收藏
淘帖
支持！
反对！