C语言实现图的广度优先搜索遍历和深度优先搜索遍历_图的广度优先搜索代码示例

1.实现存储结构为邻接矩阵的广度优先搜索遍历和深度优先搜索遍历

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MaxVertexNum 100//顶点数目的最大值
//邻接矩阵法
typedef int Type;
typedef char VexType;
//无权图用1或0表示是否相邻，带权图则为权值类型
typedef struct ArcNode{
	Type adj;
}ArcNode;
typedef struct{
	VexType Vex[MaxVertexNum];//顶点表
	ArcNode Edge[MaxVertexNum][MaxVertexNum];//边表
	int vexnum,arcnum;//图的当前顶点数和边数/弧数
}MGraph;
 
//获取顶点位置
int LocateVex(MGraph* G,VexType v){//v是查找的顶点的数据
	int k ;
	for(k = 0;k < G->vexnum;k++){
		if(G->Vex[k] == v){
			break;
		}
		//如果没有找到匹配的顶点，k的值将等于邻接矩阵的顶点数G->vexnum
	}
	return k;
}
 
//创建无向图的邻接矩阵
void CreateAdjMatrix(MGraph* G){
	int i,j,k;
	VexType v1,v2;
	printf("请输入图的顶点和弧数:");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	for(i = 0;i < G->vexnum;i++){
		//初始化邻接矩阵
		for(j = 0;j < G->vexnum;j++){
			G->Edge[i][j].adj = 0;
		}
	}
	printf("输入图的顶点：");
	for(i = 0;i < G->vexnum;i++){
		scanf(" %c",&G->Vex[i]);
	}
	for(k = 0;k < G->arcnum;k++){
		printf("输入第%d条弧的两个顶点：",k + 1);
		scanf(" %c %c",&v1,&v2);//输入一个弧的两个顶点
		i = LocateVex(G,v1);
		j = LocateVex(G,v2);
		G->Edge[i][j].adj = 1;//建立对称弧
		G->Edge[j][i].adj = 1;
	}
}
//邻接矩阵实现广度优先搜索
int Bvisited[MaxVertexNum] = {0};//访问标志数组
void BFS(MGraph G,int v0){
	int queue[MaxVertexNum];  //一维数组模拟队列操作
	int rear = 0;
	int front = 0;
	int v;//模拟队尾指针和队头指针
	printf("%c ",G.Vex[v0]);
	Bvisited[v0] = 1;
	queue[rear] = v0; //模拟入队
	while(rear >= front){
		v = queue[front];
		front++;   //模拟出队
		for(int i = 0;i < G.vexnum; i++){
			if(G.Edge[v][i].adj == 1 && !Bvisited[i]){
				printf("%c ",G.Vex[i]);
				Bvisited[i]  = 1;
				rear++;
				queue[rear] = i;  //模拟入队
			}
		}
	}
}
 
//深度优先搜索
int Dvisited[MaxVertexNum] = {0}; //访问标志数组
void DFS(MGraph G ,int v0){
	printf("%c ",G.Vex[v0]);
	Dvisited[v0] = 1;
	for(int i = 0; i < G.vexnum;i++){
		if(!Dvisited[i] && G.Edge[v0][i].adj == 1){
			DFS(G,i);
		}
	}
}
 
int main(){
	MGraph G;
	CreateAdjMatrix(&G);
	printf("广度优先搜索：");
	BFS(G,0);
	printf("\n深度优先搜索：");
	DFS(G, 0);
	return 0;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

运行截图

 注意：

        在这里广度优先遍历没有使用队列而是使用了数组代替了队列，如果使用队列可以使用顺序队列，然后使用入队和出队的代码，在这里数组其实作用差不太多

2.1.实现存储结构为邻接表的广度优先搜索遍历和深度优先搜索遍历

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MaxVertexNum 100//顶点数目的最大值
#define MaxSize 100
typedef char VertexData;
//邻接表法
typedef struct ArcNode{//边表结点
	int adjvex;//该弧所指向的顶点的位置
	struct ArcNode* next;//指向下一条弧的指针
	int info;//网的边权值
}ArcNode;
typedef struct VNode{//顶点表结点
	VertexData data;//顶点信息
	ArcNode* first;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
	AdjList vertices;//邻接表
	int vexnum,arcnum;//图的顶点数和弧数
}ALGraph;//以邻接表存储的图类型
 
//求顶点位置
int LocateVertex(ALGraph* G,VertexData v){
	int k;
	for(k = 0;k < G->vexnum;k++){
		if(G->vertices[k].data == v){
			break;
		}
	}
	return k;
}
 
//创建图的邻接表
void CreateALGraph(ALGraph* G){
	int i,j,k;
	VertexData v1,v2;
	ArcNode* p;
	printf("请输入图的顶点和弧数：");
	scanf("%d %d",&G->vexnum,&G->arcnum);
	printf("请输入图的顶点：");
	for(i = 0;i < G->vexnum;i++){//输入图的顶点，初始化顶点结点
		scanf(" %c",&(G->vertices[i].data));
		G->vertices[i].first = NULL;
	}
	for(k = 0;k < G->arcnum;k++){
		printf("输入第%d条弧的两个顶点：",k + 1);
		scanf(" %c %c",&v1,&v2);//输入一条弧的两个结点数
		i = LocateVertex(G,v1);
		j = LocateVertex(G,v2);
		p = (ArcNode*)malloc(sizeof(ArcNode));//申请新弧结点
		p->adjvex = j;
		p->next = G->vertices[i].first;
		G->vertices[i].first = p;//头插法建立链表
	}
}
 
//广度优先
int Bvisited[MaxVertexNum] = {0};
void BFS(ALGraph G,int v0){
	int queue[MaxVertexNum];
	int rear = 0,front = 0,v;
	ArcNode* p;
	printf("%c ",G.vertices[v0].data);
	Bvisited[v0] = 1;
	queue[rear] = v0;
	while(rear >= front){
		v = queue[front];
		front++;
		p = G.vertices[v].first;
		while(p != NULL){
			if(!Bvisited[p->adjvex]){
				printf("%c ",G.vertices[p->adjvex].data);
				Bvisited[p->adjvex] = 1;
				rear++;
				queue[rear] = p->adjvex;
			}
			p = p->next;
		}
	}
}
 
 
//深度优先
int Dvisited[MaxVertexNum] = {0};
void DFS(ALGraph G,int v0){
	printf("%c ",G.vertices[v0].data);
	Dvisited[v0] = 1;
	ArcNode* p;
	p = G.vertices[v0].first;
	while(p != NULL){
		if(!Dvisited[p->adjvex]){
			DFS(G,p->adjvex);
		}
		p = p->next;
	}
}
 
 
int main(){
	ALGraph G;
	CreateALGraph(&G);
	printf("\n广度优先搜索：");
	BFS(G,0);
	printf("\n深度优先搜索：");
	DFS(G,0);
	return 0;
}
 
 
 

测试可以按照上一个运行的测试样例对照