C语言-广度优先遍历

news/2024/7/15 18:37:01 标签: 队列, 数据结构, c语言, 图论, 链表
  1. 图的基本操作
  • 查找函数（LocateVex查找坐标）
  • 构建无向图（Undirected Graph）
  • 输出邻接矩阵（print）
  1. 循环队列基本操作
  • 入队（EnQueue）
  • 出队（DeQueue）
  • 判断队是否为空（QueueEmpty）
  1. 广度优先遍历：
  • 广度优先查找（BFS）
  • 广度优先遍历（BFSTraverse）

广度优先遍历基本步骤

  1. 设置全局变量visited数组并初始化为全0，代表所有节点均未被访问
  2. 设置起始点：包括对起始点进行输出、标记成已访问、入队
  3. 对后续结点进行操作：由起始点开始，对后续结点进行操作（输出、标记成已访问、入队）
    （步骤2-3为广度优先搜索）
  4. 循环重复2-3的操作避免有“孤岛”结点被遗漏。
    （步骤4 循环执行广度优先搜索避免遗漏“孤岛”结点，就是广度优先遍历）

广度优先算法分析

  1. 设定好起始点后，将起始点入队。（下代码第7-10行）
  2. 然后就是对队列进行操作了：每一个元素出队，就要将它的所有邻接点依次入队，每出一次队，就对出队元素进行操作（操作表示找到与该端点有边的端点，进行“输出，设置成已访问，入队”）直到队列为空。
void BFS(MGraph *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);//入队 
			}
		}
	} 	
}

完整源代码

1.邻接矩阵

#include <stdio.h>
#include <stdlib.h>
#define VertexMax 100 //最大顶点数为100
#define Maxsize 100 //队列最大元素个数100 

typedef char VertexType; //每个顶点数据类型为字符型 
typedef int dataType; //队列元素类型 

/*图结构体*/
typedef struct
{
	VertexType Vertex[VertexMax];//存放顶点元素的一维数组 
	int AdjMatrix[VertexMax][VertexMax];//邻接矩阵二维数组 
	int vexnum,arcnum;//图的顶点数和边数  
}MGraph;

/*队列结构体*/
typedef struct
{
	dataType *base;
	int front;
	int rear;
}CyQueue;
 
/*无向图UDG的基本操作*/
int LocateVex(MGraph *G,VertexType v)//查找元素v在一维数组 Vertex[] 中的下标，并返回下标 
{
	int i;
	
	for(i=0;i<G->vexnum;i++)
	{
		if(v==G->Vertex[i])
		{
			return i; 
		} 
	 } 
	 
	 printf("No Such Vertex!\n");
	 return -1;
}

void CreateUDG(MGraph *G) 
{
	int i,j;

	printf("输入顶点个数和边数：\n");
	printf("顶点数 n="); 
	scanf("%d",&G->vexnum);
	printf("边  数 e="); 
	scanf("%d",&G->arcnum);
	printf("\n"); 
	
	printf("\n");
	

	printf("输入顶点元素(无需空格隔开)：");
	scanf("%s",G->Vertex);
	printf("\n");

	for(i=0;i<G->vexnum;i++) 
	 for(j=0;j<G->vexnum;j++)
	    {
	    	G->AdjMatrix[i][j]=0;
		}
	

	 int n,m;
	 VertexType v1,v2;
	 
	 printf("请输入边的信息：\n");
	 for(i=0;i<G->arcnum;i++)
	 {
	 	printf("输入第%d条边信息：",i+1);
	 	scanf(" %c%c",&v1,&v2);
	 	n=LocateVex(G,v1); 
	 	m=LocateVex(G,v2); 
	 	
	 	if(n==-1||m==-1)
		 {
		 	printf("NO This Vertex!\n");
		 	return;
		  } 
	
	   G->AdjMatrix[n][m]=1;
	   G->AdjMatrix[m][n]=1;
	 } 
	 
}

void print(MGraph G)
{
	int i,j;
	printf("\n-------------------------------");
	printf("\n 邻接矩阵：\n\n"); 	

		printf("\t ");
	    for(i=0;i<G.vexnum;i++)
		printf("  %c",G.Vertex[i]);
		printf("\n");
		 
		for(i=0;i<G.vexnum;i++)
	   {
	   	  printf("\t%c",G.Vertex[i]);
	   	
		  for(j=0;j<G.vexnum;j++)
	    {
	 	    printf("  %d",G.AdjMatrix[i][j]);
	    }
	        printf("\n");
	   }
}

/*循环队列基本操作*/
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;
}

/*广度优先遍历BFS*/ 
int visited[VertexMax];//定义"标志"数组为全局变量 

void BFS(MGraph *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);//入队 
			}
		}
	} 	
} 

void BFSTraverse(MGraph *G)
{
	int i;
	
	//数组初始化为全0 
	for(i=0;i<G->vexnum;i++)
	{
		visited[i]=0;
	} 
	
	for(i=0;i<G->vexnum;i++)
	{
		if(visited[i]==0)
		{
			BFS(G,i);
		}
	}
} 

int main() 
{
	MGraph G; 
	CreateUDG(&G);
	print(G); 
	
	printf("\n\n广度优先遍历："); 
	BFSTraverse(&G); 
	 
	return 0;
}

2.邻接表：

#include <stdio.h>
#include <stdlib.h>
#define VertexMax 20 //最大顶点个数 
#define Maxsize 100 //队列最大元素个数100 

typedef char VertexType;//顶点的数据类型（char）
typedef int dataType; //队列元素类型 

/*邻接表结构体*/
typedef struct ArcNode//边表 
{
	int adjvex;//存储的是该顶点在顶点数组即AdjList[]中的位置 
	struct ArcNode *next;
}ArcNode;

typedef struct VNode //顶单个点 
{
	VertexType vertex;
	struct ArcNode *firstarc;
}VNode;

typedef struct //顶点表 
{
	VNode AdjList[VertexMax];//由顶点构成的结构体数组 
	int vexnum,arcnum; //顶点数和边数 
}ALGraph;

/*循环队列结构体*/
typedef struct
{
	dataType *base;
	int front;
	int rear;
}CyQueue;

/*无向图UDG基本操作*/
int LocateVex(ALGraph *G,VertexType v)
{    
    int i;
	for(i=0;i<G->vexnum;i++)
	{
		if(v==G->AdjList[i].vertex)
		{
			return i;
		}
	}
	
	printf("No Such Vertex!\n");
	return -1;
}

//2.无向图 
void CreateUDG(ALGraph *G)
{
	int i,j;
	//1.输入顶点数和边数
	printf("输入顶点个数和边数：\n");
	printf("顶点数 n="); 
	scanf("%d",&G->vexnum);
	printf("边  数 e="); 
	scanf("%d",&G->arcnum);
	printf("\n"); 
	
	printf("\n");
	//2.顶点表数据域填值初始化顶点表指针域
	printf("输入顶点元素(无需空格隔开)：");
	for(i=0;i<G->vexnum;i++)
	{
		scanf(" %c",&G->AdjList[i].vertex);
		G->AdjList[i].firstarc=NULL;
	} 
	printf("\n");
	
	//3.输入边信息构造邻接表
	int n,m;
	VertexType v1,v2;
	ArcNode *p1,*p2; 
	
	printf("请输入边的信息：\n\n"); 
	for(i=0;i<G->arcnum;i++)
	{   //输入边信息，并确定v1和v2在G中的位置，即顶点在AdjList[]数组中的位置（下标） 
		printf("输入第%d条边信息：",i+1); 
		scanf(" %c%c",&v1,&v2);
		n=LocateVex(G,v1);
		m=LocateVex(G,v2);
		
		if(n==-1||m==-1)
		 {
		 	printf("NO This Vertex!\n");
		 	return;
		  } 
		
		p1=(ArcNode *)malloc(sizeof(ArcNode));
		p1->adjvex=m;//填上坐标 
		p1->next=G->AdjList[n].firstarc;//改链（头插法） 
		G->AdjList[n].firstarc=p1;
		
		p2=(ArcNode *)malloc(sizeof(ArcNode));//无向图的对称 
		p2->adjvex=n;
		p2->next=G->AdjList[m].firstarc;
		G->AdjList[m].firstarc=p2;
		
	}//for 

} 

void print(ALGraph G)
{
	int i;
	ArcNode *p;
	printf("\n-------------------------------");
	printf("\n图的邻接表表示：\n");
	
	for(i=0;i<G.vexnum;i++)
	{
		printf("\n   AdjList[%d]%4c",i,G.AdjList[i].vertex);
		p=G.AdjList[i].firstarc;
		
		while(p!=NULL)
		{
			printf("-->%d",p->adjvex);
			p=p->next;
		}
	 } 
	 printf("\n");
} 

/*循环队列基本操作*/
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;
}


/*广度优先遍历*/
int visited[VertexMax]; //定义数组为全局变量 

void BFS(ALGraph *G,int i)
{
	int j;
	struct ArcNode *p;
	CyQueue q;
	create(&q);
	
    //1.设置起始点
	printf("%c",G->AdjList[i].vertex);//1.输出起始结点
	visited[i]=1;//2.将已访问的结点标志成1
	EnQueue(&q,i);//3.将第一个结点入队 

    //2.由起始点开始，对后续结点进行操作
	while(!QueueEmpty(&q))
	{
		p=G->AdjList[i].firstarc;
		
		DeQueue(&q,&i);
		while(p!=NULL)
		{
			
			if(visited[p->adjvex]==0)
			{
				printf("%c",G->AdjList[p->adjvex].vertex);
	            visited[p->adjvex]=1;
	            EnQueue(&q,p->adjvex);
			}
			p=p->next;//查找完之后，将p向后推一位 
		}
	} 	
} 

void BFSTraverse(ALGraph *G)
{
	int i;
	
	//数组初始化为全0 
	for(i=0;i<G->vexnum;i++)
	{
		visited[i]=0;
	} 
	
	for(i=0;i<G->vexnum;i++)
	{
		if(visited[i]==0)
		{
			BFS(G,i);
		}
	}
} 

int main() 
{
	ALGraph G; 
	CreateUDG(&G);
	print(G); 
	
	printf("\n\n广度优先遍历："); 
	BFSTraverse(&G); 
	 
	return 0;
}

执行结果

  • 邻接矩阵
    在这里插入图片描述
  • 邻接表
    在这里插入图片描述

http://www.niftyadmin.cn/n/1712759.html

相关文章

osl倒数第三层_计算机网络复习(最终版)

osl倒数第三层_计算机网络复习(最终版)

计算机网络复习第一章一、理解网络、互联网、因特网、万维网WWW四个概念1.网络&#xff1a;用通信线路将分散在不同地点的具有独立功能的计算机系统相互连接&#xff0c;并按网络协议进行数据通信和资源共享的计算机集合叫网络。2.互联网&#xff1a;网网相连形成互联网。3.因特…
阅读更多...
C语言-最小生成树（Prim算法）

C语言-最小生成树（Prim算法）

查找函数&#xff08;LocateVex查找坐标&#xff09;构建无向网&#xff08;Undirected Network&#xff09;输出邻接矩阵&#xff08;print&#xff09;最小值函数&#xff08;minimal&#xff09;普里姆算法&#xff08;MiniSpanTree_Prim&#xff09; 最小代价生成树背景 …
阅读更多...
c++ 进程间传递参数_Python3.8多进程之共享内存

c++ 进程间传递参数_Python3.8多进程之共享内存

最近发了个宏愿想写一个做企业金融研究的Python框架。拖出Python一看已经更新到了3.8&#xff0c;于是就发现了Python 3.8里新出现的模块&#xff1a;multiprocessing.shared_memory。随手写了个测试。生成一个240MB大小的pandas.DataFrame&#xff0c;然后转换成numpy.recarra…
阅读更多...
C语言-最小生成树（Kruskal算法）

C语言-最小生成树（Kruskal算法）

创建边集图&#xff08;CreateEdgeGraph&#xff09;打印图&#xff08;print&#xff09;排序函数&#xff08;sort&#xff09;顶点下标查找函数&#xff08;LocateVex&#xff09;查找双亲函数&#xff08;FindRoot&#xff09;克鲁斯卡尔算法&#xff08;MiniSpanTree_Krus…
阅读更多...
Unity动画篇：Mecanim动画系统重点整合（获取当前正在播放的动画片段）

Unity动画篇：Mecanim动画系统重点整合（获取当前正在播放的动画片段）

1.animator.GetCurrentAnimatorStateInfo(0); //参数是表示层级&#xff0c;返回的当前层级正在播放的动画的状态机&#xff08;Base为0&#xff0c;New为1&#xff0c;以此类推&#xff09; (如果要获取不受缩放影响的原始剪辑&#xff0c;可以用runtimeAnimatorController.…
阅读更多...
基准线_房产税呼声再起，专家“免征面积”方案获赞，超过基准线交多少？

基准线_房产税呼声再起，专家“免征面积”方案获赞，超过基准线交多少？

到目前为止&#xff0c;房子还是我国居民购买最贵的单品&#xff0c;这里指的是普通居民&#xff0c;有的富豪购买的千万豪车不算在其中。1998年我国开始了商品房“时代”&#xff0c;从此国内居民就过上了买房子生活的日子&#xff0c;而且整个房地产行业也进入了一个快速的发…
阅读更多...
Win10问题篇：解决鼠标玩游戏单击（左击/右击）失灵问题。

Win10问题篇：解决鼠标玩游戏单击（左击/右击）失灵问题。

鼠标失灵原因不外乎有三个。 1.鼠标本身问题。 2.鼠标驱动问题。 3.鼠标线材弯曲问题。 解决方法&#xff1a; 1.下载鼠标测试软件。http://dl.pconline.com.cn/download/413815.html测试是否是鼠标本身问题。 2.进入设备管理器&#xff0c;查看鼠标和其他指针设备是否有…
阅读更多...
冲压模板自动标注LISP_干货满满！超实用冲压模具资料，加薪必看！

冲压模板自动标注LISP_干货满满！超实用冲压模具资料，加薪必看！

五金模具设计 - 知乎​www.zhihu.com关注五金模具设计圈&#xff0c;一个模具人的圈子&#xff0c;看更多精彩文章及视频教程一般的冲压模具都是由&#xff1a;上下托板、上下垫脚、上下模座&#xff1a;一般用A3、Q235等“软料”做成&#xff0c;起支撑整个模具、方便架模、落…
阅读更多...
最新文章

Copyright @ 2022~2023