图的BFS（广度优先）实现C语言

桃扇骨 2023-05-28 05:17 4阅读 0赞

**实现如图（邻接矩阵）的BFS**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]  
**核心代码：**

void BFStraverse(MGraph G)
    { 
    	int i, j;
    	SqQueue Q;										//辅助队列
    	for (i = 0; i < G.numVertexes; i++)
    		visited[i] = 0;								//初始化都为0
    	InitQueue(&Q);									//初始化辅助队列
    	for (i = 0; i < G.numVertexes; i++)				//对每一个点做循环
    	{ 
    		if (!visited[i])							//若没有被访问 
    		{ 
    			visited[i] = 1;								//将当前结点设置为已访问
    			printf("%c", G.verx[i]);					//输出顶点信息
    			EnQueue(&Q, i);								//将该顶点入队列
    			while (QueueEmpty(Q))						//当前队列不为空
    			{ 
    				DeQueue(&Q, &i);						//将对头元素出队，并将其值传给i
    				for (j = 0; j < G.numVertexes; j++)
    				{ 
    					if (G.arc[i][j] == 1 && !visited[j])		//判断其他顶点若与当前顶点存在边且未被访问过
    					{ 
    						visited[j] = 1;							//标记为已访问
    						printf("%c", G.verx[j]);				//打印结点信息
    						EnQueue(&Q, j);							//将该结点入队
    					}
    				}
    			}
    		}
    	}
    }

**编译环境：vc6.0，全部代码如下：**

/* 需要一个顺序队列作为辅助 顶点数据类型为char,边上权值类型为int */
    #include <stdio.h>
    #include <stdlib.h>
    #define MAXVEX 100 //最大顶点数
    #define INFINITY 99999 //用99999表示无限大
    
    int visited[MAXVEX];				//访问标志数组,其值为1或0，1代表已访问，0代表没访问
    
    //********************邻接矩阵存储结构代码********************
    typedef struct
    { 
    	char verx[MAXVEX];					//顶点表
    	int arc[MAXVEX][MAXVEX];			//边表
    	int numVertexes, numEdges;			//图中当前顶点数和边数
    }MGraph;
    
    //********************建立无向图的邻接矩阵表示********************
    void CreateMGraph(MGraph* G)
    { 
    	int i, j, k, w;
    	printf("输入顶点数和边数\n");
    	scanf("%d%d", &G->numVertexes, &G->numEdges);
    	getchar();										//获取缓冲区的回车符
    	for (i = 0; i < G->numVertexes; i++)			//读入顶点信息
    	{ 
    		printf("输入第%d个顶点信息\n", i + 1);
    		scanf("%c", &G->verx[i]);
    		getchar();										//获取缓冲区的回车符
    	}
    	for (i = 0; i < G->numVertexes; i++)					//矩阵初始化
    		for (j = 0; j < G->numVertexes; j++)
    			if (i == j)										//如果i==j;矩阵的主对角线都为0
    				G->arc[i][j] = 0;
    			else G->arc[i][j] = INFINITY;                    //否则，矩阵初始化，都是无穷大
    	for (k = 0; k < G->numEdges; k++)						//建立邻接矩阵
    	{ 
    		printf("输入边（vi,vj）上的下标i，下标j和权w：\n");
    		scanf("%d%d%d", &i, &j, &w);				//输入边（vi,vj)上的权值w
    		G->arc[i][j] = w;
    		G->arc[j][i] = G->arc[i][j];				//因为无向图矩阵是对称的
    	}
    }
    
    //*********************队列的顺序队列存储结构*********************
    typedef struct
    { 
    	int data[MAXVEX];                                      //存放队列元素
    	int front, rear;										//队头指针和队尾指针
    }SqQueue;
    
    //**********************队列的初始化*************************
    int InitQueue(SqQueue* Q)
    { 
    	Q->front = 0;
    	Q->rear = 0;
    	return 1;
    }
    //***********************队列入队操作********************
    int EnQueue(SqQueue* Q, int e)
    { 
    	if (Q->rear == MAXVEX)						 //判断队列是否满
    		return 0;
    	Q->data[Q->rear] = e;                       //元素e赋值给队尾
    	Q->rear++;						//队尾指针后移
    	return 1;
    }
    
    //************************队列出队操作****************
    int DeQueue(SqQueue* Q, int* e)
    { 
    	if (Q->rear == Q->front)          //队空
    		return 0;
    	*e = Q->data[Q->front];            //对头元素赋值给e
    	Q->front++;                       //对头指针后移
    	return 1;
    }
    
    //************************判断队列是否为空****************
    int QueueEmpty(SqQueue Q)
    { 
    	if (Q.front == Q.rear)				//为空返回1
    		return 1;
    	else return 0;						//非空返回0
    }
    
    //********************邻接矩阵广度优先的算法********************
    void BFStraverse(MGraph G)
    { 
    	int i, j;
    	SqQueue Q;										//辅助队列
    	for (i = 0; i < G.numVertexes; i++)
    		visited[i] = 0;								//初始化都为0
    	InitQueue(&Q);									//初始化辅助队列
    	for (i = 0; i < G.numVertexes; i++)				//对每一个点做循环
    	{ 
    		if (!visited[i])							//若没有被访问 
    		{ 
    			visited[i] = 1;								//将当前结点设置为已访问
    			printf("%c", G.verx[i]);					//输出顶点信息
    			EnQueue(&Q, i);								//将该顶点入队列
    			while (QueueEmpty(Q))						//当前队列不为空
    			{ 
    				DeQueue(&Q, &i);						//将对头元素出队，并将其值传给i
    				for (j = 0; j < G.numVertexes; j++)
    				{ 
    					if (G.arc[i][j] == 1 && !visited[j])		//判断其他顶点若与当前顶点存在边且未被访问过
    					{ 
    						visited[j] = 1;							//标记为已访问
    						printf("%c", G.verx[j]);				//打印结点信息
    						EnQueue(&Q, j);							//将该结点入队
    					}
    				}
    			}
    		}
    	}
    	printf("\n");
    }
    
    
    
    int main()
    { 
    	MGraph G;
    	CreateMGraph(&G);
    	printf("广度优先遍历结果为：");
    	BFStraverse(G);
    	return 0;
    }

**输出结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/6eade73ceec448f58c774a5e793df9f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/200fcba465c44d8f8a5145c8fad4829a.png