【图的遍历算法操作】深度优先搜索遍历(DFS)和广度优先搜索遍历(BFS)
程序员文章站
2022-05-21 23:06:10
...
一、DFS
图的深度优先搜索遍历类似于二叉树的先序遍历。
基本思想是
- 首先访问出发点v,并将其标记为已访问过;
- 然后选取与v邻接的未被访问的任意一个顶点w,并且访问它;
- 再选取与w邻接的未被访问过的任意顶点并访问,以此重复。
- 当一个顶点的所有邻接点都被访问过时,依次退回到最近被访问过的顶点。
- 若该顶点还有其他邻接顶点未被访问,则从这些未被访问的顶点中取一个并重复上述过程。
二、代码
以邻接表为存储结构的图的DFS代码如下:
int visit[maxsize];
/*v是起点编号,visit[]是一个全局数组,作为顶点的访
问标记,初始时所有元素均为0,表示顶点都未被访问。因图中
可能存在回路,当前经过的顶点在将来还可能再次经过,
所以要对每个顶点进行标记*/
void DFS(AGraph *G,int v){
ArcNode *p;
visit[v]=1;
VisitNode(v);//访问顶点v操作
p=G->adjlist[v].firstarc;
while(p!=NULL){
if(visit[p->index]==0])
DFS(G,p->index);
p=p->next;
}
}
三、BFS
图的广度优先搜索遍历类似于图的层次遍历。
基本思想是:
- 首先访问起始顶点v,
- 然后选取与v邻接的全部顶点w1,w2…wn进行访问,再依次访问与w1,w2…wn邻接的全部顶点(已经访问的除外),依次类推,直到所有顶点都被访问过。
算法执行过程
- 任取图中一个顶点访问,入队,并将这个点标记为已经访问
- 当队列不空时,执行循环:出队队头,并依次检查出队顶底的所有邻接点,访问没有访问过的邻接点并入队。
- 队列为空时跳出循环,搜索完成。
四、代码
以邻接表为存储结构的图的DFS代码如下:
void BFS(AGraph *G,int v,int visit[maxsize]){
ArcNode *p;
int que[maxsize];
int front=0,rear=0;
int j;
VisitNode(v);//访问顶点v
visit[v]=1;
rear=(rear+1)%maxsize;
que[rear]=v;
while(front!=rear){
front=(front+1)%maxsize;
j=que[front];
p=G->adjlist[j].firstarc;
while(p!=NULL){
if(visit[p->index]==0){
rear=(rear+1)%maxsize;
que[rear]=p->index;
visit[p->index]=1;
VisitNode(v);//访问顶点v
}
p=p->next;
}
}
}
上一篇: 邻接表实现--图的深度优先遍历DFS和广度优先遍历BFS
下一篇: Spring Bean的初始化和销毁方法一:通过设置bean的initMethod和destroyMethod属性指定初始化和销毁方法。
推荐阅读