图：图的邻接矩阵创建、深度优先遍历和广度优先遍历详解

亦凉 2022-05-31 10:09 215阅读 0赞

# 邻接矩阵介绍 #

直接说，**邻接矩阵是图的一种存储结构**。那么图是什么呢？**图是一种逻辑结构**，和线性结构、树形结构、集合结构一样 是一种逻辑结构用来描述**数据对象中的数据元素之间的关系**。来看下图的定义：**图（Graph）是有顶点的有穷非空集和顶点之间边的集合组成，通常表示为G（V，E）其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合**。

考虑到图是有顶点和边或弧2部分组成。合在一起比较困难，那就自然的考虑到分为2个结构来分别存储。

**图的邻接矩阵（Adjacency Matrix）存储方式是用2个数组来表示图。一个一维数组存储图中顶点的信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息**。

# 邻接矩阵创建图 #

任何算法，我们最先考虑的肯定是数据结构，那么用邻接矩阵的方式，图的数据结构就很好表示了。包含顶点数组，邻接矩阵，当然还有顶点数量和边的数量。数据结构是为算法进行服务的。图的数据结构：

typedef struct  
\{  
VertexType vertex\[MAX\_VERTEX\];//顶点集  
EdgeType edge\[MAX\_VERTEX\]\[MAX\_VERTEX\];//边集  
int vertexNum, edgeNum;//顶点数，边数  
\}MGraph;

对图的数据结构清楚后，**创建图的算法，其实就是图内容的一个赋值**。

## CreateMGraph 函数 ##

//邻接矩阵创建无向网图
    MGraph* CreateMGraph()
    {
    	MGraph* mGraph = (MGraph*)malloc(sizeof(MGraph));
    	int vertexNum, edgeNum;
    	printf("请输入顶点数和边数(请用逗号隔开):");
    	scanf("%d,%d", &vertexNum, &edgeNum);
    	mGraph->vertexNum = vertexNum;
    	mGraph->edgeNum = edgeNum;
    	getchar();//去除上次输入的换行
    	printf("请输入顶点值:");
    	//输入顶点值
    	for (int i = 0; i < vertexNum; i++)
    	{
    		scanf("%c", &mGraph->vertex[i]);
    	}
    	//初始化 边集
    	for (int i = 0; i < vertexNum; i++)
    	{
    		for (int j = 0; j < vertexNum; j++)
    		{
    			mGraph->edge[i][j] = INFINITY;
    		}
    	}
    	//输入边值
    	for (int i = 0; i < edgeNum; i++)
    	{
    		int i, j, w;
    		printf("请输入(Vi,Vj)对应的顶点的下标和权值(用逗号隔开):");
    		scanf("%d,%d,%d", &i, &j, &w);
    		mGraph->edge[i][j] = mGraph->edge[j][i] = w;//无向图为对称矩阵
    	}
    	return mGraph;
    }

# 邻接矩阵的深度优先遍历 #

先说下图的遍历：**从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。那么何为深度优先遍历呢？深度优先遍历（Depth First Search），也有称为深度优先搜索，简称DFS。**想一想 因为在图中有很多条道路，怎么访问一个地方后不再访问访问过的顶点呢？其实有2种方案，就对应我们的2种遍历方式。一种方案：图中每个顶点 相连着有很多顶点，我们可以从某个结点v出发，访问此结点，然后访问v的未访问过的邻阶点，然后继续访问该结点 的未访问过的邻接点，有点类似顺藤摸瓜的意思，一直深入，直到图中所有的顶点都被访问到为止。是不是感觉可以用递归呢？肯定要用一个**全局数组来记录顶点是否访问过呗**，访问过下次就不访问了呗。下面是邻接矩阵的深度优先遍历：

void DFTMGraph(MGraph* graph,int vexIndex)
    {
    	//访问过 就不再进行访问
    	if (g_visited[vexIndex] == TRUE)
    	{
    		return;
    	}
    	g_visited[vexIndex] = TRUE;
    	//对访问到的结点进行操作
    	VisitMGraphVertex(graph->vertex[vexIndex]);
    
    	for (int j = 0; j < graph->vertexNum; j++)
    	{
    		//权值不为零，继续访问下一个结点
    		if (graph->edge[vexIndex][j] != 0)
    		{
    			DFTMGraph(graph, j);
    		}
    	}
    	return;
    }
    
    //深度优先遍历
    void TraverseMGraph(MGraph* graph)
    {
    	if (NULL == graph)
    	{
    		return;
    	}
    	//设置结点都没有访问过
    	for (int i = 0; i < graph->vertexNum; i++)
    	{
    		g_visited[i] = FALSE;
    	}
    	for (int i = 0; i < graph->vertexNum; i++)
    	{
    		if (g_visited[i] == FALSE)
    		{
    			DFTMGraph(graph,i);
    		}
    	}
    	return;
    }

# 邻接矩阵的广度优先遍历 #

**广度优先遍历（Breath First Search），又称为广度优先搜索，检测BFS**。它很类似层序遍历，从图中某结点v出发，将该结点没有访问过的邻接点访问一遍，然后访问已经访问过结点的未访问过的邻结点访问一遍，直到图中的所有结点被访问完。下面是邻接矩阵的广度优先遍历：

//广度优先遍历 邻接矩阵
    void BFTMGraph(MGraph* graph)
    {
    	Queue queue;
    	InitQueue(&queue);
    	for (int i = 0; i < graph->vertexNum; i++)
    	{
    		g_visited[i] = FALSE;
    	}
    	for (int i = 0; i < graph->vertexNum; i++)
    	{
    		if (g_visited[i] == FALSE)
    		{
    			g_visited[i] = TRUE;
    			VisitMGraphVertex(graph->vertex[i]);
    			EnQueue(&queue,i);//当前结点下标入队
    			//为什么这里要循环出队呢？出队获取已经访问过结点的下标，在内层的for继续访问相关联结点，将减少外层for循环进入if次数
    			while (!EmptyQueue(&queue))
    			{
    				int vexIndex;
    				DeQueue(&queue, &vexIndex);//访问过的结点下标出队
    				for (int j = 0; j < graph->vertexNum; j++)
    				{
    					//将该节点的连接的结点且没有被访问过的结点访问，然后入队
    					if (graph->edge[vexIndex][j] != 0 && graph->edge[vexIndex][j] != INFINITY && g_visited[j] == FALSE)
    					{
    						g_visited[j] = TRUE;
    						VisitMGraphVertex(graph->vertex[j]);
    						EnQueue(&queue, graph->vertex[j]);
    					}
    				
    				}
    			}
    
    			
    		}
    	}
    	return;
    }

# 代码汇总 #

## Queue.h ##

#pragma once
    #ifndef __QUEUE_H__
    #define __QUEUE_H__
    
    typedef int EleType;//元素类型
    typedef enum { ERROR, OK } Status;
    typedef enum {FALSE,TRUE} Boolean;
    
    //队列结点
    typedef struct QueueNode
    {
    	EleType data;
    	struct QueueNode* next;
    }QueueNode;
    
    //队列
    typedef struct Queue
    {
    	QueueNode* front;
    	QueueNode* tail;
    }Queue;
    
    //队列初始化
    void InitQueue(Queue* queue);
    
    //入队
    int EnQueue(Queue* queue, EleType data);
    
    //出队
    int DeQueue(Queue* queue, EleType* data);
    
    //队列是否为空
    int EmptyQueue(Queue* queue);
    
    #endif // !__QUEUE_H__

## Queue.c ##

#include <stdlib.h>
    #include "Queue.h"
    
    
    //队列初始化
    void InitQueue(Queue* queue)
    {
    	queue->front = NULL;
    	queue->tail = NULL;
    	return;
    }
    
    //入队
    int EnQueue(Queue* queue, EleType data)
    {
    	if (NULL == queue)
    	{
    		return ERROR;
    	}
    	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    	node->data = data;
    	node->next = NULL;
    	if (queue->front == NULL)
    	{
    		queue->front = queue->tail = node;
    	}
    	else
    	{
    		queue->tail->next = node;
    		queue->tail = node;
    	}
    	return OK;
    }
    //出队
    int DeQueue(Queue* queue, EleType* data)
    {
    	if (NULL == queue)
    	{
    		return ERROR;
    	}
    	if (!EmptyQueue(queue))
    	{
    		QueueNode* node = queue->front;
    		*data = node->data;
    		queue->front = queue->front->next;
    		if (NULL != node)
    		{
    			free(node);
    			node = NULL;
    		}
    		//队列的最后一个元素出队列后，tail指针也要置为空
    		if (EmptyQueue(queue))
    		{
    			queue->tail = queue->front;
    		}
    	}
    	return OK;
    }
    
    //队列是否为空
    int EmptyQueue(Queue* queue)
    {
    	if (NULL == queue)
    	{
    		return ERROR;
    	}
    	if (queue->front == NULL)
    	{
    		return TRUE;
    	}
    	return FALSE;
    }

## MGraph.c ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "Queue.h"
    #define MAX_VERTEX 100
    #define INFINITY 65535
    typedef char VertexType;//顶点类型
    typedef int EdgeType;//边上权值类型
    typedef struct
    {
    	VertexType vertex[MAX_VERTEX];//顶点集
    	EdgeType edge[MAX_VERTEX][MAX_VERTEX];//边集
    	int vertexNum, edgeNum;//顶点数，边数
    }MGraph;
    Boolean g_visited[MAX_VERTEX] = {0};//全局变量 顶点访问标志位数组
    //邻接矩阵创建无向网图
    MGraph* CreateMGraph()
    {
    	MGraph* mGraph = (MGraph*)malloc(sizeof(MGraph));
    	int vertexNum, edgeNum;
    	printf("请输入顶点数和边数(请用逗号隔开):");
    	scanf("%d,%d", &vertexNum, &edgeNum);
    	mGraph->vertexNum = vertexNum;
    	mGraph->edgeNum = edgeNum;
    	getchar();//去除上次输入的换行
    	printf("请输入顶点值:");
    	//输入顶点值
    	for (int i = 0; i < vertexNum; i++)
    	{
    		scanf("%c", &mGraph->vertex[i]);
    	}
    	//初始化 边集
    	for (int i = 0; i < vertexNum; i++)
    	{
    		for (int j = 0; j < vertexNum; j++)
    		{
    			mGraph->edge[i][j] = INFINITY;
    		}
    	}
    	//输入边值
    	for (int i = 0; i < edgeNum; i++)
    	{
    		int i, j, w;
    		printf("请输入(Vi,Vj)对应的顶点的下标和权值(用逗号隔开):");
    		scanf("%d,%d,%d", &i, &j, &w);
    		mGraph->edge[i][j] = mGraph->edge[j][i] = w;//无向图为对称矩阵
    	}
    	return mGraph;
    }
    //打印邻接矩阵的无向图数据
    void PrintMGraph(MGraph* mGraph)
    {
    	printf("顶点数组数据:\n");
    	for (int i = 0; i < mGraph->vertexNum; i++)
    	{
    		printf("%c ", mGraph->vertex[i]);
    	}
    	printf("\n边点数组数据:\n");
    	for (int i = 0; i < mGraph->vertexNum; i++)
    	{
    		for (int j = 0; j < mGraph->vertexNum; j++)
    		{
    			printf("%d\t", mGraph->edge[i][j]);
    		}
    		printf("\n");
    	}
    }
    //访问顶点元素
    void VisitMGraphVertex(VertexType data)
    {
    	printf("%c ",data);
    	return;
    }
    
    void DFTMGraph(MGraph* graph,int vexIndex)
    {
    	//访问过 就不再进行访问
    	if (g_visited[vexIndex] == TRUE)
    	{
    		return;
    	}
    	g_visited[vexIndex] = TRUE;
    	//对访问到的结点进行操作
    	VisitMGraphVertex(graph->vertex[vexIndex]);
    
    	for (int j = 0; j < graph->vertexNum; j++)
    	{
    		//权值不为零，继续访问下一个结点
    		if (graph->edge[vexIndex][j] != 0)
    		{
    			DFTMGraph(graph, j);
    		}
    	}
    	return;
    }
    
    //深度优先遍历
    void TraverseMGraph(MGraph* graph)
    {
    	if (NULL == graph)
    	{
    		return;
    	}
    	//设置结点都没有访问过
    	for (int i = 0; i < graph->vertexNum; i++)
    	{
    		g_visited[i] = FALSE;
    	}
    	for (int i = 0; i < graph->vertexNum; i++)
    	{
    		if (g_visited[i] == FALSE)
    		{
    			DFTMGraph(graph,i);
    		}
    	}
    	return;
    }
    //广度优先遍历 邻接矩阵
    void BFTMGraph(MGraph* graph)
    {
    	Queue queue;
    	InitQueue(&queue);
    	for (int i = 0; i < graph->vertexNum; i++)
    	{
    		g_visited[i] = FALSE;
    	}
    	for (int i = 0; i < graph->vertexNum; i++)
    	{
    		if (g_visited[i] == FALSE)
    		{
    			g_visited[i] = TRUE;
    			VisitMGraphVertex(graph->vertex[i]);
    			EnQueue(&queue,i);//当前结点下标入队
    			//为什么这里要循环出队呢？出队获取已经访问过结点的下标，在内层的for继续访问相关联结点，将减少外层for循环进入if次数
    			while (!EmptyQueue(&queue))
    			{
    				int vexIndex;
    				DeQueue(&queue, &vexIndex);//访问过的结点下标出队
    				for (int j = 0; j < graph->vertexNum; j++)
    				{
    					//将该节点的连接的结点且没有被访问过的结点访问，然后入队
    					if (graph->edge[vexIndex][j] != 0 && g_visited[j] == FALSE)
    					{
    						g_visited[j] = TRUE;
    						VisitMGraphVertex(graph->vertex[j]);
    						EnQueue(&queue, graph->vertex[j]);
    					}
    				
    				}
    			}
    
    			
    		}
    	}
    	return;
    }
    
    int main(int argc, char *argv[])
    {
    	MGraph* mGraph = CreateMGraph();
    	PrintMGraph(mGraph);
    	printf("深度优先遍历邻接矩阵:\n");
    	TraverseMGraph(mGraph);
    	printf("\n广度优先遍历邻接矩阵:\n");
    	BFTMGraph(mGraph);
    	printf("\n");
    	return 0;
    }

# 代码运行检测 #

我们来创建如下图 的一个图，图是教材上的。

![Center][]

代码运行结果：

![Center 1][]

[Center]: /images/20220531/1dd7e3b11b5649d58328a9bcd8f24438.png
[Center 1]: /images/20220531/81c916f55194488cbc4ec51178176050.png