图：图的邻接表创建、深度优先遍历和广度优先遍历代码实现

短命女 2022-05-31 10:10 202阅读 0赞

# 邻接表介绍 #

**邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构比较较浪费存储空间**。**如果不想浪费存储空间，大家肯定会先到链表**。需要空间的时候再才想内存去申请，同样适用于图的存储。**我们把这种数组与链表相结合的存储方式成为邻接表（Adjacency List）**。关于**邻接矩阵**的详细介绍请看：[图：图的邻接矩阵创建、深度优先遍历和广度优先遍历详解][Link 1] 。

# 邻接表创建图 #

我们**创建边表的单链表时，可以使用头插法和尾插法创建，不过尾插法要麻烦一点，需要先创建头结点，最后还要释放头结点，不过2种方法 效果一样**。

//邻接表创建无向网图
    GraphAdjList* CreateGraphAdjList()
    {
    	GraphAdjList* graph = (GraphAdjList*)malloc(sizeof(GraphAdjList));
    	int vexNum, edgeNum;
    	printf("请输入顶点和边数(用逗号隔开):");
    	scanf("%d,%d",&vexNum,&edgeNum);
    	graph->edgeNun = edgeNum;
    	graph->vexNum = vexNum;
    	getchar();//消除上面的换行符
    	printf("请输入顶点的值:");
    	输入顶点值
    	//for (int i = 0; i < vexNum; i++)
    	//{
    	//	scanf("%c", &graph->list[i].data);
    	//	graph->list[i].first = NULL;//初始化first指针域
    	//}
    	输入边表数据
    	//for (int k = 0; k < edgeNum; k++)
    	//{
    	//	int i, j, w;
    	//	printf("请输入(Vi,Vj)对应的顶点下标和权值(用逗号隔开):");
    	//	scanf("%d,%d,%d", &i, &j, &w);
    	//	//i -> j i出度到j
    	//	EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//创建边结点
    	//	edge->vexIndex = j;
    	//	edge->weight = w;
    	//	edge->next = graph->list[i].first;//头插法 往单链表插入结点
    	//	graph->list[i].first = edge;
    	//	//由于是无向的，实现上是双向的，故边数据(Vj,Vi)也要创建
    	//	//j -> i j出度到i
    	//	edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    	//	edge->vexIndex = i;
    	//	edge->weight = w;
    	//	edge->next = graph->list[j].first;;
    	//	graph->list[j].first = edge;
    
    	//}
    
    	//每个单链表的尾指针数组
    	EdgeNode** tailArr = (EdgeNode**)malloc(sizeof(EdgeNode*)*vexNum);
    	//输入顶点值
    	for (int i = 0; i < vexNum; i++)
    	{
    		scanf("%c", &graph->list[i].data);
    		graph->list[i].first = (EdgeNode*)malloc(sizeof(EdgeNode));//创建头结点，采用尾插入
    		graph->list[i].first->next = NULL;
    		tailArr[i] = graph->list[i].first;
    	}
    	//输入边表数据
    	for (int k = 0; k < edgeNum; k++)
    	{
    		int i, j, w;
    		printf("请输入(Vi,Vj)对应的顶点下标和权值(用逗号隔开):");
    		scanf("%d,%d,%d", &i, &j, &w);
    		//i -> j i出度到j
    		EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//创建边结点
    		edge->vexIndex = j;
    		edge->weight = w;
    		edge->next = NULL;
    		tailArr[i]->next = edge;	//采用尾插法
    		tailArr[i] = edge;
    
    		edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    		edge->vexIndex = i;
    		edge->weight = w;
    		edge->next = NULL;
    		tailArr[j]->next = edge;
    		tailArr[j] = edge;
    	}
    	//将头结点释放
    	for (int i = 0; i < vexNum; i++)
    	{
    		EdgeNode* head = graph->list[i].first;
    		graph->list[i].first = head->next;
    		free(head);
    	}
    	return graph;
    }

# 邻接表的深度优先遍历 #

void DFTGraphAdjList(GraphAdjList* graph,int vexIndex)
    {
    	//访问过不再访问
    	if (g_visited[vexIndex] == TRUE)
    	{
    		return;
    	}
    	g_visited[vexIndex] = TRUE;
    	VisitGraphAdjListVertex(graph->list[vexIndex].data);
    
    	EdgeNode* node = graph->list[vexIndex].first;
    	while (node)
    	{
    		DFTGraphAdjList(graph, node->vexIndex);
    		node = node->next;
    	}
    	return;
    }
    
    //深度优先遍历邻接表
    void TraverseGraphAdjList(GraphAdjList* graph)
    {
    	if (NULL == graph)
    	{
    		return;
    	}
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		g_visited[i] = FALSE;
    	}
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		if (g_visited[i] == FALSE)
    		{
    			DFTGraphAdjList(graph, i);
    		}
    	}
    
    	return;
    }

# 邻接表的广度优先遍历 #

//广度优先遍历邻接表
    void BFTGraphAdjList(GraphAdjList* graph)
    {
    
    	if (NULL == graph)
    	{
    		return;
    	}
    	Queue queue;
    	InitQueue(&queue);
    	//初始化顶点都没有访问过
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		g_visited[i] = FALSE;
    	}
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		if (g_visited[i] == FALSE)
    		{
    			g_visited[i] = TRUE;
    			VertexType vex = graph->list[i].data;
    			VisitGraphAdjListVertex(vex);//访问顶点数据
    			EnQueue(&queue, i);//将访问过的顶点下标入队
    			//为什么这里要循环出队呢？出队获取已经访问过结点的下标，在内层的for继续访问其相关联结点，将减少外层for循环进入if次数
    			while (!EmptyQueue(&queue))
    			{
    				int vexIndex;
    				DeQueue(&queue, &vexIndex);//将访问过的顶点下标出队
    				EdgeNode* node = graph->list[vexIndex].first;
    				//将该节点的连接的结点且没有被访问过的结点进行访问，然后入队
    				while (node != NULL && g_visited[node->vexIndex] == FALSE)
    				{
    					g_visited[node->vexIndex] = TRUE;
    					VertexType vex = graph->list[node->vexIndex].data;
    					VisitGraphAdjListVertex(vex);
    					EnQueue(&queue, node->vexIndex);
    					node = node->next;
    				}
    			}
    
    		}
    	}
    	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;
    }

## GraphAdjList.c ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "Queue.h"
    #define MAX_VERTEX 100
    typedef char VertexType;//顶点类型
    typedef int EdgeType;//边上权值类型
    //边表结点数据结构
    typedef struct EdgeNode
    {
    	int vexIndex;//顶点下标
    	EdgeType weight;//权值
    	struct EdgeNode* next;	//指向下一个结点
    }EdgeNode;
    Boolean g_visited[MAX_VERTEX] = { 0 };//全局变量 顶点访问标志位数组
    //顶点表数据结构
    typedef struct VextexNode
    {
    	VertexType data;
    	EdgeNode* first;//边表第一个结点
    }VextexNode,AdjList[MAX_VERTEX];
    
    typedef struct GraphAdjList
    {
    	AdjList list;
    	int vexNum, edgeNun;//顶点，边 的数量
    }GraphAdjList;
    
    //邻接表创建无向网图
    GraphAdjList* CreateGraphAdjList()
    {
    	GraphAdjList* graph = (GraphAdjList*)malloc(sizeof(GraphAdjList));
    	int vexNum, edgeNum;
    	printf("请输入顶点和边数(用逗号隔开):");
    	scanf("%d,%d",&vexNum,&edgeNum);
    	graph->edgeNun = edgeNum;
    	graph->vexNum = vexNum;
    	getchar();//消除上面的换行符
    	printf("请输入顶点的值:");
    	输入顶点值
    	//for (int i = 0; i < vexNum; i++)
    	//{
    	//	scanf("%c", &graph->list[i].data);
    	//	graph->list[i].first = NULL;//初始化first指针域
    	//}
    	输入边表数据
    	//for (int k = 0; k < edgeNum; k++)
    	//{
    	//	int i, j, w;
    	//	printf("请输入(Vi,Vj)对应的顶点下标和权值(用逗号隔开):");
    	//	scanf("%d,%d,%d", &i, &j, &w);
    	//	//i -> j i出度到j
    	//	EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//创建边结点
    	//	edge->vexIndex = j;
    	//	edge->weight = w;
    	//	edge->next = graph->list[i].first;//头插法 往单链表插入结点
    	//	graph->list[i].first = edge;
    	//	//由于是无向的，实现上是双向的，故边数据(Vj,Vi)也要创建
    	//	//j -> i j出度到i
    	//	edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    	//	edge->vexIndex = i;
    	//	edge->weight = w;
    	//	edge->next = graph->list[j].first;;
    	//	graph->list[j].first = edge;
    
    	//}
    
    	//每个单链表的尾指针数组
    	EdgeNode** tailArr = (EdgeNode**)malloc(sizeof(EdgeNode*)*vexNum);
    	//输入顶点值
    	for (int i = 0; i < vexNum; i++)
    	{
    		scanf("%c", &graph->list[i].data);
    		graph->list[i].first = (EdgeNode*)malloc(sizeof(EdgeNode));//创建头结点，采用尾插入
    		graph->list[i].first->next = NULL;
    		tailArr[i] = graph->list[i].first;
    	}
    	//输入边表数据
    	for (int k = 0; k < edgeNum; k++)
    	{
    		int i, j, w;
    		printf("请输入(Vi,Vj)对应的顶点下标和权值(用逗号隔开):");
    		scanf("%d,%d,%d", &i, &j, &w);
    		//i -> j i出度到j
    		EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//创建边结点
    		edge->vexIndex = j;
    		edge->weight = w;
    		edge->next = NULL;
    		tailArr[i]->next = edge;	//采用尾插法
    		tailArr[i] = edge;
    
    		edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    		edge->vexIndex = i;
    		edge->weight = w;
    		edge->next = NULL;
    		tailArr[j]->next = edge;
    		tailArr[j] = edge;
    	}
    	//将头结点释放
    	for (int i = 0; i < vexNum; i++)
    	{
    		EdgeNode* head = graph->list[i].first;
    		graph->list[i].first = head->next;
    		free(head);
    	}
    	return graph;
    }
    //打印 邻接表的无向图
    void PrintGraphAdjList(GraphAdjList* graph)
    {
    	printf("顶点数据:\n");
    	//顶点数据
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		printf("%c ",graph->list[i].data);
    	}
    	printf("\n边数据:\n");
    	EdgeNode* temp = NULL;
    	//边数据
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		temp = graph->list[i].first;
    		while (temp)
    		{
    			printf("%d\t",temp->weight);
    			temp = temp->next;
    		}
    		printf("\n");
    	}
    	return;
    }
    //访问顶点元素
    void VisitGraphAdjListVertex(VertexType data)
    {
    	printf("%c ", data);
    	return;
    }
    void DFTGraphAdjList(GraphAdjList* graph,int vexIndex)
    {
    	//访问过不再访问
    	if (g_visited[vexIndex] == TRUE)
    	{
    		return;
    	}
    	g_visited[vexIndex] = TRUE;
    	VisitGraphAdjListVertex(graph->list[vexIndex].data);
    
    	EdgeNode* node = graph->list[vexIndex].first;
    	while (node)
    	{
    		DFTGraphAdjList(graph, node->vexIndex);
    		node = node->next;
    	}
    	return;
    }
    
    //深度优先遍历邻接表
    void TraverseGraphAdjList(GraphAdjList* graph)
    {
    	if (NULL == graph)
    	{
    		return;
    	}
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		g_visited[i] = FALSE;
    	}
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		if (g_visited[i] == FALSE)
    		{
    			DFTGraphAdjList(graph, i);
    		}
    	}
    
    	return;
    }
    //广度优先遍历邻接表
    void BFTGraphAdjList(GraphAdjList* graph)
    {
    
    	if (NULL == graph)
    	{
    		return;
    	}
    	Queue queue;
    	InitQueue(&queue);
    	//初始化顶点都没有访问过
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		g_visited[i] = FALSE;
    	}
    	for (int i = 0; i < graph->vexNum; i++)
    	{
    		if (g_visited[i] == FALSE)
    		{
    			g_visited[i] = TRUE;
    			VertexType vex = graph->list[i].data;
    			VisitGraphAdjListVertex(vex);//访问顶点数据
    			EnQueue(&queue, i);//将访问过的顶点下标入队
    			//为什么这里要循环出队呢？出队获取已经访问过结点的下标，在内层的for继续访问其相关联结点，将减少外层for循环进入if次数
    			while (!EmptyQueue(&queue))
    			{
    				int vexIndex;
    				DeQueue(&queue, &vexIndex);//将访问过的顶点下标出队
    				EdgeNode* node = graph->list[vexIndex].first;
    				//将该节点的连接的结点且没有被访问过的结点进行访问，然后入队
    				while (node != NULL && g_visited[node->vexIndex] == FALSE)
    				{
    					g_visited[node->vexIndex] = TRUE;
    					VertexType vex = graph->list[node->vexIndex].data;
    					VisitGraphAdjListVertex(vex);
    					EnQueue(&queue, node->vexIndex);
    					node = node->next;
    				}
    			}
    
    		}
    	}
    	return;
    }
    
    
    int main(int argc, char *argv[])
    {
    	GraphAdjList* graph = CreateGraphAdjList();
    	PrintGraphAdjList(graph);
    	printf("深度优先遍历邻接表:\n");
    	TraverseGraphAdjList(graph);
    	printf("\n广度优先遍历邻接表:\n");
    	BFTGraphAdjList(graph);
    	printf("\n");
    	return 0;
    }

# 代码运行测试 #

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

![Center][]

代码运行结果：

![Center 1][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79340112
[Center]: /images/20220531/1759dc9f1503455ca566db3695558bbc.png
[Center 1]: /images/20220531/06b9a819f24a49b09bffecacae301192.png