图的遍历之深度优先遍历DFS

古城微笑少年丶 2023-03-12 12:19 14阅读 0赞

GraphBasicOperation.cpp文件链接：[https://blog.csdn.net/qq\_16261421/article/details/106005857][https_blog.csdn.net_qq_16261421_article_details_106005857]

深度优先搜索遍历的过程是：

（1）从图中某个初始顶点*v*出发，首先访问初始顶点*v*。

（2）选择一个与顶点*v*相邻且没被访问过的顶点*w*为初始顶点，再从*w*出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。　**　**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70][]

#include "GraphBasicOperation.cpp"
    void BFS(ALGraph *G,int v)  
    {
    	ArcNode *p;
    	int queue[MAXV],front=0,rear=0;			//定义循环队列并初始化
    	int visited[MAXV];            			//定义存放结点的访问标志的数组
    	int w,i;
    	for (i=0;i<G->n;i++) visited[i]=0;		//访问标志数组初始化
    	printf("%2d",v); 						//输出被访问顶点的编号
    	visited[v]=1;              				//置已访问标记
    	rear=(rear+1)%MAXV;
    	queue[rear]=v;             				//v进队
    	while (front!=rear)       				//若队列不空时循环
    	{	
    		front=(front+1)%MAXV;
    		w=queue[front];       				//出队并赋给w
    		p=G->adjlist[w].firstarc; 			//找与顶点w邻接的第一个顶点
    		while (p!=NULL) 
    		{	
    			if (visited[p->adjvex]==0) 		//若当前邻接顶点未被访问
    			{
    				printf("%2d",p->adjvex);  	//访问相邻顶点
    				visited[p->adjvex]=1;		//置该顶点已被访问的标志
    				rear=(rear+1)%MAXV;			//该顶点进队
    				queue[rear]=p->adjvex;
               	}
               	p=p->nextarc;              		//找下一个邻接顶点
    		}
    	}
    	printf("\n");
    }
    void main()
    {
    	int i,j;
    	MGraph g;
    	ALGraph *G;
    	int A[MAXV][5]={
    		{0,1,0,1,1},
    		{1,0,1,1,0},
    		{0,1,0,1,1},
    		{1,1,1,0,1},
    		{1,0,1,1,0}};
    	g.n=5;g.e=16;
    	for (i=0;i<g.n;i++)
    		for (j=0;j<g.n;j++)
    			g.edges[i][j]=A[i][j];
    	G=(ALGraph *)malloc(sizeof(ALGraph));	
    	MatToList(g,G);
    	printf(" 邻接表:\n");DispAdj(G);
    	printf("广度优先序列:");BFS(G,2);printf("\n");
    }

[https_blog.csdn.net_qq_16261421_article_details_106005857]: https://blog.csdn.net/qq_16261421/article/details/106005857
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70]: /images/20230312/37105dd96ba949c1a68f6693d346aeb6.png