数据结构——图的基本定义以及图的存储结构，邻接矩阵，邻接表-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构——图的基本定义以及图的存储结构，邻接矩阵，邻接表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

图的定义和术语

图的存储结构

顺序存储结构—邻接矩阵

链式存储结构

邻接表

邻接多重表

十字链表

图的遍历

图的连通性问题

有向无环图及其应用

最短路径

图的定义和术语

图的定义：图是一种非线性的复杂的数据结构，图中的数据元素的关系是多对多的关系，在图中我们常常把数据元素称作顶点，图是由一个非空的顶点集和V（vertex：顶点）和一个描述顶点之间邻接关系的边集合E（edge：边）组成，E中的每条边所连接的两个顶点必须属于集合V。
形式化定义：对于图而言其边集合E可以是空集，此时的图只有顶点而没有边
无向图：若边集合中的边<v,w>之间是没有顺序的即<v,w>,<w,v>表示的是同一条边，那么就称该图为无向图
有向图：若边集合E中的边<v,w>之间是有顺序的，即<v,w>,<w,v>表示的是两条不同的边，那么就称该图为有向图；<v,w>表示以v为起点，以w为终点的一条弧，v叫做弧尾，w叫做弧头（可以这样理解，有箭头的一端为弧头），在有向图中我们把边称作弧，而无向图中就叫做边
弧：在有向图中表示两个顶点之间存在一个关系，用序偶对<v,w>来表示
边：在无向图中表示两个顶点之间存在一个关系，有序对(v,w)来表示
简单图：在无向图中不存在顶点到其自身的边，且同一条边不重复出现，如：
无向完全图：任意两个顶点之间都存在边，也就是任意两个顶点之间都存在关系的无向图称作无向完全图。对于无向完全图图而言，其边的条数为n(n-1)/2，这很容易理解，用笔谢谢就可以明白了。
有向完全图：任意两个顶点之间都存在相反方向的弧的有向图叫做有向完全图，有向完全图中的弧的数目为：n(n-1)
稠密图和稀疏图：边或者弧很少的图叫做稀疏图，反之就叫做稠密图，规定边e<nlogn的图就叫做稀疏图，n表示顶点个数
权（weight）：与图的边或者弧有关的数叫做权，权可以用来表示两个顶点之间的距离或者耗费。
网：边或者弧上带上权值的图叫做网，也叫做网图或者带权图
邻接点：对于无向图而言，若顶点v，w之间存在边，那么就称v和w互为邻接点，或者叫做v和w相关联。
无向图的顶点的度：对于无向图而言，其顶点的度是指与该顶点相关联的边的数目
有向图的顶点的度：有向图中某个顶点的度包括该顶点的出度和入度，顶点的出度是指以该顶点作为起点的弧的条数，顶点的入度是指以该顶点作为终点的弧的条数，有向图中顶点的度是指顶点的出度与顶点的入度之和
对于图而言，其顶点的度之和的一半的就是图的边或者弧的数目。即：
路径：路径是指从一个顶点v，到另一个顶点w所经过的顶点的集合，是一个有序的序列，以v为序列起点，以w为序列终点
路径长度：路径中边的数目称作路径的长度，如：
回路：若一条路径的始点和终点是同一个顶点，那么该条路径就构成一个回路
简单路径：若路径中的顶点不重复出现，那么就称该路径为简单路径
简单回路：在一个回路中除了起点和终点外其它顶点不重复出现，那么就称该回路为简单回路。
连通：在无向图中如果从一个顶点v到另一个顶点w之间有路径，那么就称顶点v和w之间是连通的
连通图：对于无向图而言，若其任意两个顶点之间都是连通的那么我们就称该无向图为连通图
连通分量：无向图的极大连通子图，对于连通图而言其连通分量就是自己，而对于非连通无向图而言，其连通分量，需要包含其所能包含的最大的顶点数，且是各顶点之间都是连通的连通分量是对无向图的一种划分
强连通图：对于有向图而言，若对于任意一对顶点(v,w)而言，若从顶点v->w与从顶点w->v均有路径，则称该有向图为强连通图
弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。
强连通分量：有向图的极大强连通子图，对于有向强连通图而言，其强连通分量就是其本身。：
无向连通图的生成树：无向连通图的生成树是该无向连通图的一个极小的连通子图，所谓无向连通图的极小连通子图是指包含该无向连通图全部顶点且含有最小的边的数目的图，即再多加一条边就会在图中形成环，而再少一条边该子图就不连通了，n个顶点的无向连通图G的生成树是这样一棵树，该树中的结点包含了G中的所有顶点，且其含有n-1条边，以及其所对应的图是连通的，再多一条边在其所对应的图中会形成环，而再少一条边该树所对应的图就不连通了。如：
无向图的生成树的特点：

一个含有n个顶点的无向连通图，其生成树含有n个顶点，n-1条边
如果一个无向图含有n个顶点，但是其边的数目却小于n-1那么该无向图一定不是连通的
如果一个含有n个顶点的无向图中含有不少于n条边，那么该无向图中一定含有环
若一个含有n个顶点的无向图，那么由该无向图生成的含有n-1条边的图不一定是生成树，结合图就很容易理解

30.生成森林：在非连通图中，由每一个连通分量所得到的生成树所构成的森林。

31.有向图的生成森林：有向图的生成森林是指这样一些子图所构成的森林，由若干棵有向树所组成，这些有向树包含了该有向图的全部的顶点。所谓有向树是指，只有一个顶点入度为0，而其它的顶点入度都为1的有向图。如：邻接矩阵定义,C语言学习历程,算法,数据结构,图论,c语言,程序人生

32.网络：连通的带权图（包括弱连通图）叫做网络

图的存储结构

顺序存储结构—邻接矩阵

邻接矩阵的定义：对于一个含有n个顶点的图，我们用一个一维数组来存储其顶点信息，用一个二维数组来存储其边或者弧的信息，或者也可以认为所存储的边或者弧是两个顶点之间的关系，那么该二维数组就叫做邻接矩阵
无向无权图的顺序存储结构：对于一个含有n个顶点的无向无权图，我们用一个大小为n的一维数组vertex来存储其顶点的信息，然后用一个n x n大小的二维数组edge来存放其边的信息，对于二维数组edge的位置（i，j）处的元素的值这样定义，若顶点vertex[i]和顶点vertex[j]之间有边，那么edge[i][j]的值就为1，否则edge[i][j]的值就为0，所以对于无向无权图而言，其邻接矩阵是n阶对称方阵，这很容易理解，如：
无向有权图的顺序存储结构：对于含有n个顶点的无向有权图而言，我们用一个大小为n的一维数组vertex来存储其顶点的信息，然后用一个n x n大小的二维数组edge来存储其边的信息，对于二维数组edge中的元素的值我们这样定义，对于二维数组中的位置（i，j）处的元素的值，若顶点vertex[i]和顶点vertex[j]之间有一条带权的边，那么二维数组edge中位置（i，j）处的元素的值就为该条边的权值，否则该位置处的元素值就为无限大，所以对于无向带权图而言其邻接矩阵也是一个n阶的对称方阵。如：
无向图的邻接矩阵的特点：无向图的邻接矩阵是一个n阶的对称方阵，对于无向无权图而言顶点vertex[i]的度是邻接矩阵中第i行或者第i列中非0元素的个数，而对于无向带权图而言，其顶点vertex[i]的度是第i行或者第i列中值不为无穷的元素的个数，无向带权图的邻接矩阵中下三角或者上三角中非无穷大元素的个数就是无向有权图的边的条数，而无向无权图的邻接矩阵的下三角或者上三角中的非0元素的个数就是无向无权图的边的条数。
有向无权图的顺序存储结构：对于含有n个顶点的有向无权图而言，我们用一个大小为n的一维数组来存放其顶点信息，用一个大小为n x n的二维数组edge来存储其弧的信息，对于二维数组中的元素的值我们这样定义，对于位置（i，j）处的元素的值，若vertex[i]->vertex[j]有弧那么二维数组edge中位置（i，j）处元素的值就为1，反之则为0，对于二位数组edge中位置（j，i）处元素的值，若vertex[j]->vertex[i]有弧那么二维数组edge的位置（j，i）处的元素的值就为1，反之则为0，和无向无权图的邻接矩阵的定义差不多只不过有向无权图中的弧有方向，而无向无权图中的边没有方向，如：
有向带权图的顺序存储结构：对于一个含有n个顶点的有向带权图而言，我们用一个大小为n的一维数组vertex来存放其顶点信息，用一个大小为n x n的二维数组edge来存放其弧的信息，对于二维数组edge中的元素的值我们这样定义，对于二维数组edge中位置（i，j）处的值，若vertex[i]->vertex[j]有一条带权的弧，那么edge[i][j]的值就为该带权弧的权值，否则edge[i][j]的值就为无穷大，对于edge中位置（j，i）处元素的值，若vertex[j]->vertex[i]处有一条带权的弧，那么edge[j][i]的值就为该条带权的弧的权值，反之则为无穷大,如：
有向图的邻接矩阵的特点：有向图的邻接矩阵不一定是对称阵，对于无权有向图而言某一个顶底i的出度是邻接矩阵中第i行非0元素的个数，而顶点i的入度是邻接矩阵中第i列中非0元素的个数，对于有向带权图而言，某个顶点i的出度是邻接矩阵中第i行中非无穷元素的个数，而顶点i的入度是邻接矩阵中第i列中非无穷元素的个数，邻接矩阵中非0元素或者非无穷元素的个就是该有向图的弧的条数。
邻接矩阵的优点：用邻接矩阵存储图的边或者弧的信息有便于对图的操作，比如求某个顶点的度，或者求某个顶点的邻接点，边或者弧的信息等等
邻接矩阵的缺点：对于一个有n个顶点的图而言需要n x n大小的二维数组来存储其边或者弧的信息，对于稀疏图而言其很浪费存储空间

用C语言数组实现图的邻接矩阵存储

创建如图所示的几个图，分别为无向图，无向网，有向图，有向网

邻接矩阵定义,C语言学习历程,算法,数据结构,图论,c语言,程序人生

将图的顶点信息用一维数组表示，而图的边或者弧的信息用二维数组来表示即图的邻接矩阵来表示，我们将图的类型定义为枚举类型，将图定义为结构体类型，在结构体中存储图的顶点信息，邻接矩阵，图的类型，图中顶点的数目以及边或者弧的数目，如下定义了图的结构：

#define MVnum 20           //定义最大的顶点数量

//定义图的类型，无向无权图简记为无向图UDG，无向带权图即无向网UDN,有向无权图简记为有向图DG，有向带权图即有向网DN,D是direction的首字母大写
typedef enum Gkind{UDG=1,UDN,DG,DN}Gkind;  
//在C语言中枚举类型被当作整数类型或者无符号整型来处理，所以枚举类型相当于是为一组离散的整数取一个别名，取别名的目的是为了见名知意  

//定义图，将其定义成结构体类型，在结构体中显示处图的种类，图中含有边或者弧的条数，以及顶点信息用一维数组来表示，边或者弧用一个二维数组来表示，即用邻接矩阵来表示


typedef struct graphic
{
	Gkind kind;           //图的类型，无向图，无向网，有向图，有向网
	char VInfo[MVnum];           //存储图的顶点信息
	int Adjacency_matrix[MVnum][MVnum];        //邻接矩阵存储图的边或者弧的信息
	int vnum;       //图的顶点的数目
	int EaNum;      //图的边或者弧的数目
}G,*Graphic;

定义好图结构之后就需要定义一个函数来创建图，如下函数用于创建图：

void Create_Graphic(Graphic g)
{
	//输入你所需要创建的图的种类
	Gkind k;
	printf("请输入你所需要创建的图的种类，1代表无向图，2代表无向网，3代表有向图，4代表有向网\n");
	scanf("%d", &k);
	g->kind = k;
	
	//依次输入图的顶点的数目和图的数目
	printf("请输入图中所含有的顶点的数目以及边或者弧的数目\n");
	scanf("%d%d", &(g->vnum), &(g->EaNum));

	getchar();
	
	//输入图的顶点信息
	printf("请输入图中的顶点元素的值：\n");
	for (int i = 0; i < g->vnum; i++)
	{
		scanf("%c", &(g->VInfo[i]));
		getchar();
	}
	
	
	//输入边或者弧的信息，即某两个顶点之间是否存在边或者存在弧；
	switch (k)
	{
	case UDG:printf("判断图中两个顶点之间是否存在边，若存在则输入1，若不存在则输入0\n"); break;
	case UDN:printf("判断图中两个顶点之间是否存在边，若存在则输入边的权值大小，若不存在则输入-1\n"); break;
	case DG:printf("判断图中两个顶点之间是否存在弧，若存在则输入1，若不存在则输入0\n"); break;
	case DN:printf("判断图中两个顶点之间是否存在弧，若存在则输入弧的权值大小若不存在则输入-1\n");
	default:break;
	}
	for (int i = 0; i < g->vnum; i++)
	{
		for (int j = 0; j < g->vnum; j++)
		{
			printf("%c->%c：", g->VInfo[i], g->VInfo[j]);
			scanf("%d", &g->Adjacency_matrix[i][j]);
		}
	}
	printf("图创建成功\n");


}

完整的程序源代码，以及运行结果截图

//图的顺序存储结构之邻接矩阵

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define MVnum 20           //定义最大的顶点数量

//定义图的类型，无向无权图简记为无向图UDG，无向带权图即无向网UDN,有向无权图简记为有向图DG，有向带权图即有向网DN,D是direction的首字母大写
typedef enum Gkind{UDG=1,UDN,DG,DN}Gkind;  
//在C语言中枚举类型被当作整数类型或者无符号整型来处理，所以枚举类型相当于是为一组离散的整数取一个别名，取别名的目的是为了见名知意  

//定义图，将其定义成结构体类型，在结构体中显示处图的种类，图中含有边或者弧的条数，以及顶点信息用一维数组来表示，边或者弧用一个二维数组来表示，即用邻接矩阵来表示


typedef struct graphic
{
	Gkind kind;           //图的类型，无向图，无向网，有向图，有向网
	char VInfo[MVnum];           //存储图的顶点信息
	int Adjacency_matrix[MVnum][MVnum];        //邻接矩阵存储图的边或者弧的信息
	int vnum;       //图的顶点的数目
	int EaNum;      //图的边或者弧的数目
}G,*Graphic;

//以下函数用于创建图
void Create_Graphic(Graphic g);

int main()
{
	G Mygraphic;
	Graphic mg = &Mygraphic;
	Create_Graphic(mg);
	printf("所创建的图的顶点信息：\n");
	for (int i = 0; i < mg->vnum; i++)
	{
		printf("%c ", mg->VInfo[i]);
		
	}
	printf("\n所创建的图的边的信息即图的邻接矩阵\n");
	for (int i = 0; i < mg->vnum; i++)
	{
		for (int j = 0; j < mg->vnum; j++)
		{
			printf("%d ", mg->Adjacency_matrix[i][j]);
		}
		printf("\n");
	}

	
	return 0;

}

void Create_Graphic(Graphic g)
{
	//输入你所需要创建的图的种类
	Gkind k;
	printf("请输入你所需要创建的图的种类，1代表无向图，2代表无向网，3代表有向图，4代表有向网\n");
	scanf("%d", &k);
	g->kind = k;
	
	//依次输入图的顶点的数目和图的数目
	printf("请输入图中所含有的顶点的数目以及边或者弧的数目\n");
	scanf("%d%d", &(g->vnum), &(g->EaNum));

	getchar();
	
	//输入图的顶点信息
	printf("请输入图中的顶点元素的值：\n");
	for (int i = 0; i < g->vnum; i++)
	{
		scanf("%c", &(g->VInfo[i]));
		getchar();
	}
	
	
	//输入边或者弧的信息，即某两个顶点之间是否存在边或者存在弧；
	switch (k)
	{
	case UDG:printf("判断图中两个顶点之间是否存在边，若存在则输入1，若不存在则输入0\n"); break;
	case UDN:printf("判断图中两个顶点之间是否存在边，若存在则输入边的权值大小，若不存在则输入-1\n"); break;
	case DG:printf("判断图中两个顶点之间是否存在弧，若存在则输入1，若不存在则输入0\n"); break;
	case DN:printf("判断图中两个顶点之间是否存在弧，若存在则输入弧的权值大小若不存在则输入-1\n");
	default:break;
	}
	for (int i = 0; i < g->vnum; i++)
	{
		for (int j = 0; j < g->vnum; j++)
		{
			printf("%c->%c：", g->VInfo[i], g->VInfo[j]);
			scanf("%d", &g->Adjacency_matrix[i][j]);
		}
	}
	printf("图创建成功\n");


}

运行结果截图，测试用例中给出了创建四种图，即无向图，无向网，有向图，有向网的测试结果：

邻接矩阵定义,C语言学习历程,算法,数据结构,图论,c语言,程序人生

链式存储结构

邻接表

若我们直接去看书那么书上对邻接表的定义是这样的：邻接表是图的一种链式存储结构，在邻接表中，对图中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图而言是以顶点vi为尾的弧），每个结点由三个域组成，其中邻接点域（adjvex）指示与顶点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或者弧的结点；数据域存储的是与边或者弧有关的信息如权值信息等；每个链表附设一个表头节点，在表头结点中除了设有链域（firstarc）指向单链表的第一个节点以外还有存储顶点vi有关的信息的数据域；

直接去看书上对于邻接表的定义可能会觉得有点难以理解，其实是这样的，我们为无向图中的每一个顶点建立一个单链表，该单链表具有表头结点，表头结点有两个域，一个是数据域用于存放该顶点的值信息，另一个域是指针域，这个指针域指向我们为该顶点建立的单链表的第一个结点，也就是第一个非表头结点，然后将我们为所有顶点建立的单链表的头节点存储在一维数组中，按照顺序存储，既然是为每一个顶点建立一个单链表那么此单链表除了表头结点之外还有其他节点，图中某个顶点vi的单链表除了表头结点之外的其他节点是用于存放无向图边的信息的，顶点vi的单链表除了表头结点之外的其它结点的节点结构和顶点vi的单链表表头结点的结点结构不一样，其它结点的结点结构有两个数据域，一个数据域adjvex是用于存放与该顶点邻接的第一个顶点在数组中的位置也就是下标，而另一个数据域info是用于存放与边相关的信息的，比如权值信息，若没有权值这个数据域可以不要，有一个指针域nextarc用于指向下一个结点，下一个节点的数据域adjvex存放的是与顶点vi邻接的第二个顶点在数组中的下标，info域存放与边有关的信息，如权值信息，若不带取值这个域可以不要，指针域指向单链表中的下一个节点，如此往复直到将与顶点vi邻接的顶点信息都加入到单链表中为止，如图所示结合例子来理解将会更容易理解：邻接矩阵定义,C语言学习历程,算法,数据结构,图论,c语言,程序人生

对于有向图而言我们需要建立两个邻接表，一个是正邻接表用于存储以顶点vi为弧尾即以vi作为始点的弧的信息，而另一个邻接表称为逆邻接表，用于存放以顶点vi作为终点的弧的信息

用C语言实现图的邻接表即链式存储结构

创建如图所示的有向图，用图的链式存储结构邻接表来存储此图邻接矩阵定义,C语言学习历程,算法,数据结构,图论,c语言,程序人生

由于所需要创建的图是有向图所以需要两个邻接表来存储此图，分别是正邻接表和逆邻接表，正邻接表用于存储以某个顶点为起点的弧的信息，而你邻接表用于存储以某个顶点为终点的弧的信息

第一步构造邻接表的非头节点结构以及头节点结构以即定义图的结构体结构：


//定义顶点的单链表非头节点节点结构，创建的图是有向无权图，所以非表头结点的节点结构的数据域只有一个，用于存放与该顶点邻接的顶点在数组中的位置即数组下标，没有了数据域info，info是用于存放弧的权值信息的
typedef struct ArcNode
{
	int adj_position;   //用于存放以该顶点为始点的邻接点在数组中的下标
	struct ArcNode* nextarc;  //存放下一个结点的信息


}ArcNode, * AN;

//定义图的顶点的头节点结构
typedef struct HeadNode
{
	char data;        //头节点的数据域用于存放图的顶点信息
	AN Pfirstarc;          //指向该顶点的正邻接表的第一个结点
	AN IVfirstarc;         //指向该顶点的逆邻接表的第一个结点

}HeadNode, * HN;

//定义图的结构体类型
typedef struct DG
{
	HeadNode hv[N];               //将图的顶点单链表的头节点用一维数组顺序存放
	int vnum;        //用于存放图的定点数量
	int arcnum;     //用于存放图的弧的数量
}DG,*dg;

构造好图的结构之后，我们需要一个函数用于为图的每一个顶点创建单链表，由于是有向图,所以实际上需要创建两个单链表，一个单链表存放的是以该顶点为起点的弧的信息，另一个单链表存放的是以该顶点为终点的弧的信息

void Create_LinkList(HN h,int o)          //o示我们要为数组中的哪一个顶点创建单链表
{


	//建立正向邻接表
	AN p = (AN)malloc(sizeof(ArcNode)), q;
	q = p;
	//为节点的数据域输入值，直到输入-1表示单链表创建完毕
	printf("请输入以顶点%c作为始点的邻接点在数组中的下标：\n", h->data);
	scanf("%d", &p->adj_position);
	
	
	while (p->adj_position != -1)
	{
		
		if (h->Pfirstarc == NULL)
		{
			h->Pfirstarc = p;
		}
		else
		{
			q->nextarc = p;
			q = q->nextarc;
		}
		p = (AN)malloc(sizeof(ArcNode));	
		printf("请输入以顶点%c为始点的下一个邻接点在数组中的下标：\n", h->data);
		scanf("%d", &p->adj_position);
	}
	
	
	//建立逆向邻接表
	q = p;
	//为节点的数据域输入值，直到输入-1表示单链表创建完毕
	printf("请输入以顶点%c作为终点的邻接点在数组中的下标：\n", h->data);
	scanf("%d", &p->adj_position);


	while (p->adj_position != -1)
	{

		if (h->IVfirstarc == NULL)
		{
			h->IVfirstarc = p;
		}
		else
		{
			q->nextarc = p;
			q = q->nextarc;
		}
		p = (AN)malloc(sizeof(ArcNode));
		printf("请输入以顶点%c为终点的下一个邻接点在数组中的下标：\n", h->data);
		scanf("%d", &p->adj_position);
	}

	
	printf("第顶点%c的正单链表和逆单链表均创建成功\n", h->data);
	return;
	

}

之后就是创建图了

void Create_DG(dg mydg, int n)
{
	mydg->vnum = n;
	printf("请输入该有向无权图的弧的数目：\n");
	scanf("%d", &(mydg->arcnum));
	
	getchar();
	//注意先将头节点的指针域设置为空指针
	for (int i = 0; i < n; i++)
	{
		printf("请输入第%d个顶点的值：\n", i + 1);
		scanf("%c", &(mydg->hv[i]).data);
		(mydg->hv[i]).Pfirstarc = NULL;
		(mydg->hv[i]).IVfirstarc = NULL;
		getchar();
	}

	//为每一个顶点创建单链表
	for (int i = 0; i < n; i++)
	{
		Create_LinkList(&(mydg->hv[i]), i);
	}


	printf("图创建成功\n");
	return;


}

完整程序源代码



//图的链式存储结构实现，邻接表,

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 6

//定义顶点的单链表非头节点节点结构，创建的图是有向无权图，所以非表头结点的节点结构的数据域只有一个，用于存放与该顶点邻接的顶点在数组中的位置即数组下标，没有了数据域info，info是用于存放弧的权值信息的
typedef struct ArcNode
{
	int adj_position;   //用于存放以该顶点为始点的邻接点在数组中的下标
	struct ArcNode* nextarc;  //存放下一个结点的信息


}ArcNode, * AN;

//定义图的顶点的头节点结构
typedef struct HeadNode
{
	char data;        //头节点的数据域用于存放图的顶点信息
	AN Pfirstarc;          //指向该顶点的正邻接表的第一个结点
	AN IVfirstarc;         //指向该顶点的逆邻接表的第一个结点

}HeadNode, * HN;

//定义图的结构体类型
typedef struct DG
{
	HeadNode hv[N];               //将图的顶点单链表的头节点用一维数组顺序存放
	int vnum;        //用于存放图的定点数量
	int arcnum;     //用于存放图的弧的数量
}DG,*dg;



///以下函数用于创建一个单链表
void Create_LinkList(HN a,int o);

//以下函数用于创建图
void Create_DG(dg mydg,int n);


int main()
{
	int n;
	printf("请输入图中的顶点个数\n");
	scanf("%d", &n);
	
	DG g;
	dg my_dg = &g;
	Create_DG(my_dg, n);

	return 0;

}

void Create_LinkList(HN h,int o)          //o示我们要为数组中的哪一个顶点创建单链表
{


	//建立正向邻接表
	AN p = (AN)malloc(sizeof(ArcNode)), q;
	q = p;
	//为节点的数据域输入值，直到输入-1表示单链表创建完毕
	printf("请输入以顶点%c作为始点的邻接点在数组中的下标：\n", h->data);
	scanf("%d", &p->adj_position);
	
	
	while (p->adj_position != -1)
	{
		
		if (h->Pfirstarc == NULL)
		{
			h->Pfirstarc = p;
		}
		else
		{
			q->nextarc = p;
			q = q->nextarc;
		}
		p = (AN)malloc(sizeof(ArcNode));	
		printf("请输入以顶点%c为始点的下一个邻接点在数组中的下标：\n", h->data);
		scanf("%d", &p->adj_position);
	}
	
	
	//建立逆向邻接表
	q = p;
	//为节点的数据域输入值，直到输入-1表示单链表创建完毕
	printf("请输入以顶点%c作为终点的邻接点在数组中的下标：\n", h->data);
	scanf("%d", &p->adj_position);


	while (p->adj_position != -1)
	{

		if (h->IVfirstarc == NULL)
		{
			h->IVfirstarc = p;
		}
		else
		{
			q->nextarc = p;
			q = q->nextarc;
		}
		p = (AN)malloc(sizeof(ArcNode));
		printf("请输入以顶点%c为终点的下一个邻接点在数组中的下标：\n", h->data);
		scanf("%d", &p->adj_position);
	}

	
	printf("第顶点%c的正单链表和逆单链表均创建成功\n", h->data);
	return;
	

}

void Create_DG(dg mydg, int n)
{
	mydg->vnum = n;
	printf("请输入该有向无权图的弧的数目：\n");
	scanf("%d", &(mydg->arcnum));
	
	getchar();
	//注意先将头节点的指针域设置为空指针
	for (int i = 0; i < n; i++)
	{
		printf("请输入第%d个顶点的值：\n", i + 1);
		scanf("%c", &(mydg->hv[i]).data);
		(mydg->hv[i]).Pfirstarc = NULL;
		(mydg->hv[i]).IVfirstarc = NULL;
		getchar();
	}

	//为每一个顶点创建单链表
	for (int i = 0; i < n; i++)
	{
		Create_LinkList(&(mydg->hv[i]), i);
	}


	printf("图创建成功\n");
	return;


}

程序运行结果截图

邻接矩阵定义,C语言学习历程,算法,数据结构,图论,c语言,程序人生