欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【图的遍历算法操作】深度优先搜索遍历(DFS)和广度优先搜索遍历(BFS)

程序员文章站 2022-05-21 23:06:10
...

一、DFS
图的深度优先搜索遍历类似于二叉树的先序遍历。
基本思想是

  1. 首先访问出发点v,并将其标记为已访问过;
  2. 然后选取与v邻接的未被访问的任意一个顶点w,并且访问它;
  3. 再选取与w邻接的未被访问过的任意顶点并访问,以此重复。
  4. 当一个顶点的所有邻接点都被访问过时,依次退回到最近被访问过的顶点。
  5. 若该顶点还有其他邻接顶点未被访问,则从这些未被访问的顶点中取一个并重复上述过程。

二、代码
以邻接表为存储结构的图的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;
		}
	}
}