图的遍历(C语言)

  • Post author:
  • Post category:其他




图的遍历

和树的遍历类似,图的遍历也是从图中某一顶点出发,按照某种方法对图中所有顶点访问且仅访问一次。图的遍历又比树的遍历复杂得多。因为图的任一顶点都可能和其余的顶点相邻接。所以在访问了某个顶点之后,可能沿着某条路径搜索之后,又回到该顶点上。根据搜索路径的方向,通常有两条遍历图的路径:深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。



深度优先搜索



概念

深度优先搜索遍历类似于树的先序遍历,是树的先序遍历的推广

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。讲通俗一点,深度优先搜索其实像在走迷宫,遇到一个岔路口,先选则一条路,当发现这条路是死路时,又返回岔路口选择第二条路,直至找到出口。



过程

对于一个连通图,深度优先搜索遍历过程:

1.从图中某个顶点v出发,访问v;

2.找出刚刚访问过的顶点的第一个未被访问的邻接点,访问该顶点。以该顶点为新顶点,重复该步骤,直至刚访问过的顶点没有未被访问的邻接点为止;(递归思想)

3.返回前一个访问过的且仍有未被访问的邻接点的顶点,找出该顶点的下一个未被访问的邻接点,访问该顶点;

4.重复第2、3步骤,直至图中所有顶点都被访问过,搜索结束。

遍历过程具体如下图:



(1)从顶点v1出发,访问v1;

(2)在访问顶点v1之后,选择第一个未被访问的邻接点v2,访问v2。以v2为新顶点,重复此步,访问v4,v8,v5。在访问v5之后,由于v5的邻接点都已被访问,此步结束;

(3)搜索从v5回到v8,由于同样的理由,搜索继续回到v4,v2直到v1,此时由于v1的另一个邻接点未被访问,则又从v1到v3,再继续进行下去。

由此得到的顶点访问序列为:

v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7

(访问的具体过程如下图)

在这里插入图片描述

在这里插入图片描述



算法实现

深度优先搜索过程遍历连通图是一个递归过程,为了在遍历过程中便于区分顶点是否已被访问,需要附设访问标志数组visited[n],其初值为“false”,一旦某个顶点被访问,则其相应的分量置为”true”。代码如下:

#define MaxVertices 100 
#define MAX_VERTEX_NUM 10 
typedef struct node{ //边表 
	int adjvex; 
	struct node* next; 
}EdgeNode; 
typedef struct{ //顶点表 
	int vertex; 
	EdgeNode* edgenext; 
}VertexNode; 
typedef VertexNode AdjList[MaxVertices]; 
typedef struct{ 
	AdjList adjlist;
	int n,e; 
}AdjMatrix; 
int visited[MAX_VERTEX_NUM]; 
void DFS(AdjMatrix *G, int v) { 
	EdgeNode *p; 	
	printf("->%c",G->adjlist[v].vertex); 
	visited[v]=1; 
	p=G->adjlist[v].edgenext; 
	while (p) { 
		if(!visited[p->adjvex]) DFS(G,p->adjvex); 
		p=p->next; 
	} 
} //从第v个顶点出发DFS 
void DFSTraverse(AdjMatrix *G) {  
	int v;
	for(v=0;v<G->n;++v) 
		visited[v]=0; 
	for(v=0;v<G->n;++v) 
		if(!visited[v]) DFS(G,v);//递归调用 
		printf("\n\n"); 
}//DFSTraverse 



广度优先搜索



概念

广度优先搜索遍历类似于树的按层次遍历的过程。广度优先搜索算法(又称宽度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。



过程

对于连通图(图如上深度搜索的连通图)

1.从图中某个顶点出发,访问v;

2.依次访问v的各个未曾访问过的邻接点;

3.分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”被访问。重复步骤3,直至图中所有已被访问的顶点的邻接点都被访问到。

具体的例子如下图:

在这里插入图片描述

(1)从顶点v1出发,访问v1;

(2)依次访问v1的各个未被访问过的邻接点v2和v3;

(3)依次访问v2的各个邻接点v4和v5,以及v3的邻接点v6和v7,最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问,并且图中所有顶点都被访问,由此完成了图的遍历。得到顶点的访问序列为:

v1 -> v2 -> v3 -> v4 -> v5 -> v6 -> v7 -> v8

(具体访问过程如下图)

在这里插入图片描述



算法实现

广度优先搜索的特点是:尽可能先对横向进行搜索。设x和y是两个相继被访问过的顶点,若当前以x为出发点进行搜索,则在访问x的所有未被访问过的邻接点之后,紧接着是以y为出发点进行横向搜索,并对搜索到的y的邻接点中尚未被访问的顶点进行访问。也就是说,先访问的顶点其邻接点亦先被访问。为此,算法实现时需要引进队列保存已被访问过的顶点。

#define bool char
#define true 1
#define false 0//定义bool类型的数
bool visited[100];//访问标志数组,其初值为"false"
//bool为一种数据类型,其值只有两个true和false,只有在面向对象的语言中有这种类型的数据类型,在c语言中不存在,但是我们可以自己定义
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef int  ArcType;//假设边的权值类型为整型
struct AMGraph{
	VerTexType vexs[100];//顶点表
	ArcType arcs[100][100];//;邻接矩阵
	int vexnum,arcnum;//图的当前点数和边数
};
void create(CyQueue *q) {  
	q->base=(dataType *)malloc(Maxsize*sizeof(dataType));  
	if(!q->base)  {   
		printf("Space allocation failed!\n");   
		return; 
	}  
	q->front=q->rear=0;  
	return; 
}
void EnQueue(CyQueue *q,dataType value) {  
	if((q->rear+1)%Maxsize==q->front)  
	{   
		printf("Cyclic Queue is Full!\n");   
		return;  
		}  
	q->base[q->rear]=value;
	q->rear=(q->rear+1)%Maxsize;  
	return; 
} 
void DeQueue(CyQueue *q,dataType *value) {  
	if(q->front==q->rear)  
	{   
		printf("Cyclic Queue is Empty!\n");   
		return;  
		}  
	*value=q->base[q->front];  
	q->front=(q->front+1)%Maxsize;  
	return; 
} 
int QueueEmpty(CyQueue *q) { 
	if (q->front==q->rear)//队列为空返回1,不为空返回0  
	{ 
		return 1; 
		} 
	return 0; 
}
void BFS(struct AMGraph *G,int i) {  
	int j;  
	CyQueue q;  
	create(&q);   //1.设置起始点  
	printf("%c",G->Vertex[i]);//1.输出起始结点  
	visited[i]=1;//2.将已访问的结点标志成1  
	EnQueue(&q,i);//3.将第一个结点入队 
	//2.由起始点开始,对后续结点进行操作  
	while(!QueueEmpty(&q))//队列非空  
	{      
		DeQueue(&q,&i);    
		for(j=0;j<G->vexnum;j++)   {   
			 if(G->AdjMatrix[i][j]==1&&visited[j]==0)    {
			      printf("%c",G->Vertex[j]);//输出符合条件的顶点   
				  visited[j]=1;//设置成已访问状态1   
				  EnQueue(&q,j);//入队   
			   }	   
			}  
		} 
  } 



总结

深度优先搜索算法的实现运用的主要是回溯法,类似于树的先序遍历算法。

广度优先搜索算法借助队列的先进先出的特点,类似于树的层次遍历。



版权声明:本文为weixin_52044227原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。