数据结构—图的遍历BFS、DFS
图的遍历算法可以用来判断图的连通性。
对于无向图来说,访问图中所有顶点所需调用BFS/DFS的次数就是连通分量数。但是对于有向图来说,具体问题需要具体分析,对于强连通图,只需调用一次,但是对于非强连通图就要具体分析。
0、图的存储结构定义
-
//图的邻接矩阵存储结构定义
-
#define MaxVerNum 100 //顶点数目的最大值
-
typedef struct{
-
char Vex[MaxVerNum]; //顶点表
-
int Edge[MaxVerNum][MaxVerNum]; //邻接矩阵,边表
-
int vexnum,archnum; //图的当前顶点数和弧数
-
}Graph;
-
-
//图的邻接表存储结构定义
-
#define MaxVerNum 100 //顶点数目的最大值
-
typedef struct ArcNode{ //边表结点
-
int adjvex; //该弧所指向的顶点的位置
-
struct ArcNode *next; //指向下一条弧的指针
-
int num; //图的权值
-
}ArcNode;
-
typedef struct VNode{ //顶点表信息
-
char data; //顶点信息
-
ArcNode *first; //指向第一条依附于该顶点的弧的指针
-
}VNode,AdjList[MaxVerNum];
-
typedef struct{
-
AdjList vertices; //邻接表
-
int vexnum,arcnum; //图的顶点数和弧数
-
}Graph;
1、图的广度优先遍历(BFS)
图的广度优先遍历算法思想和二叉树的层次遍历算法思想几乎是相同的,需要一个辅助队列实现。
-
//广度优先遍历
-
bool visit[Maxnum]; //标记数组,防止顶点被多次访问
-
void BFSTraverse(Graph G)
-
{
-
for(int i=0;i<G.vexnum;i ) //对标记数组进行初始化
-
{
-
visit[i]=false;
-
}
-
InitQueue(Q); //初始化辅助队列
-
for(int i=0;i<G.vexnum;i ) //对每个连通分量调用一次BFS
-
{
-
if(!visit[i])
-
BFS(G,i);
-
}
-
}
-
void BFS(Graph G,int v)
-
{
-
visit[v]; //访问
-
visit[v]=True; //标记
-
EnQueue(Q,v); //顶点v入队
-
while(!isEmpty(Q))
-
{
-
DeQueue(Q,v); //访问完出队
-
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,V,W)) //寻找顶点v的所有邻接点
-
{
-
if(!visit[w])
-
{
-
visit[w];
-
visit[w]=true;
-
EnQueue(Q,w);
-
}
-
}
-
}
-
}
时间复杂度:邻接表:O(|V| |E|);邻接矩阵:O(|V|^2);
空间复杂度为:O(|V|);主要来自于辅助队列
由广度优先遍历得到的遍历树称为:广度优先遍生成树。对于非连通图的广度优先遍历可得到广度优先森林。
2、图的深度优先遍历(DFS)
图的深度优先遍历算法思想和二叉树的先序遍历算法思想几乎相同。由于该算法是一个递归算法,所以它需要借助一个递归工作栈。
-
//图的深度优先遍历
-
bool visit[Maxnum]; //标记数组,防止顶点被多次访问
-
void DFSTraverse(Graph G)
-
{
-
for(int i=0;i<G.vexnum;i )
-
{
-
visit[i]=false;
-
}
-
for(int i=0;i<G.vexnum;i )
-
{
-
if(!visit[i])
-
DFS(G,i);
-
}
-
}
-
void DFS(Graph G,int v)
-
{
-
visit[v];
-
visit[v]=true;
-
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,V,W)) //从顶点v出发,深度优先遍历G
-
{
-
if(!visit[w]);
-
DFS(G,w);
-
}
-
}
时间复杂度:邻接表:O(|V| |E|);邻接矩阵:O(|V|^2);
空间复杂度:O(|V|);主要来自于递归工作栈。
深度优先搜索对连通图会产生深度优先生成树,对不连通图的深度优先遍历会产生深度优先森林。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfckjb
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01