文章目录
- 【 1. 图的顺序存储结构 】
- 1.1 基本原理
- 1.2 顺序存储结构的 C 实现
- 【 2. 图的链式存储结构 】
- 2.1 图的临接表存储结构
- 2.1.1 临接表的 基本原理
- 2.1.2 临接表的 链表节点
- 2.1.3 邻接表 各结构体的C实现
- 2.1.4 临接表 计算顶点的出度和入度
- 邻接表计算 无向图的出度和入度
- 邻接表计算 有向图的出度和入度
- 2.2 图的十字链表存储结构
- 2.2.1 十字链表的 基本原理
- 2.2.2 十字链表的 链表节点
- 2.2.3 十字链表的 C实现
- 2.3 图的临接多重表存储结构
- 2.3.1 临接多重表的 基本原理
- 2.3.2 临接多重表的 链表节点
- 2.3.3 临接多重表的 C 实现
- 【 3. 图的各存储结构的对比 】
【 1. 图的顺序存储结构 】
1.1 基本原理
- 图可以采用顺序存储（也就是使用 数组 有效地存储），使用数组存储图时，需要使用 两个数组：
- 数据数组：存放图中顶点本身的数据（一维数组：存储图中各顶点本身数据，使用一维数组就足够了）；
- 临接矩阵（关系数组）：用于存储各顶点之间的关系（二维数组：存储顶点之间的关系时，要记录每个顶点和其它所有顶点之间的关系，所以需要使用二维数组）。临接矩阵中值的确定如下：
- 在使用二维数组存储 无权值 的图 中顶点之间的关系时，如果顶点之间 存在边或弧，在相应位置用 1 表示，反之用 0 表示；
- 如果使用二维数组存储 有权值 的图即网 中顶点之间的关系，顶点之间如果 有边或者弧的存在，在数组的相应位置存储其权值；反之用 0 表示。
- 数组 可用于存储 无向图 和 有向图 。
例如：存储下图中的两张图时，除了存储图中各顶点本身具有的数据外，还需要使用二维数组存储任意两个顶点之间的关系。
- 存储上图中的有向图（A）时，对应的二维数组如下图所示：
例如，arcs[0][1] = 1 ，证明从 V1 到 V2 有弧存在。且通过该矩阵，可以很轻松得知各顶点的出度和入度，出度为该行非 0 值的和，入度为该列非 0 值的和。例如，V1 的出度为第一行两个 1 的和 为 2 ； V1 的入度为第一列中 1 的和 为 1 。所以 V1 的出度为 2 ，入度为 1 ，度为两者的和 3 。
- 存储上上图中的无向图（B）时，由于各顶点没有权值，所以如果两顶点之间有关联，相应位置记为 1 ；反之记为 0 。构建的二维数组如下图所示：
在此二维数组中，每一行代表一个顶点，依次从 V1 到 V5 ，每一列也是如此。比如 arcs[0][1] = 1 ，表示 V1 和 V2 之间有边存在；而 arcs[0][2] = 0，说明 V1 和 V3 之间没有边。通过该矩阵，可以直观地判断出各个顶点的度，为该行（或该列）非 0 值的和。例如，第一行有两个 1，说明 V1 有两个边，所以度为 2。
1.2 顺序存储结构的 C 实现
- 在此程序中，构建无向网或有向网时，对于之间没有边或弧的顶点，相应的二阶矩阵中存放的是 0，目的只是为了方便查看运行结果。而实际上 如果顶点之间没有关联，则关系数组对应位置上的值应该是无穷大 ∞，以表示距离无穷远，根本无法到达 。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#define MAX_VERtEX_NUM 20 //顶点的最大个数
#define VertexType int //顶点的数据类型
#define VRType int //表示顶点之间的关系的变量类型
#define InfoType char //存储弧或者边额外信息的指针变量类型
typedef enum { DG, DN, UDG, UDN }GraphKind; //枚举图的 4 种类型：0无权有向、1无权无向、2有权有向、3有权无向
// 边/弧 的信息结构体，包括权值和附加其他信息
typedef struct {
VRType adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
InfoType* info; //弧或边额外含有的信息指针
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];
//图结构体
typedef struct {
VertexType vexs[MAX_VERtEX_NUM]; //一维数据数组
AdjMatrix arcs; //二维关系数组（邻接矩阵），每个元素为1个ArcCell信息结构体
int vexnum, arcnum; //图的顶点数和 弧/边 数
GraphKind kind; //图的种类
}MGraph;
//根据顶点本身数据值，判断出顶点在二维数组中的位置
int LocateVex(MGraph* G, VertexType v) {
int i = 0;
//遍历一维数组，找到变量v
for (; i < G->vexnum; i++) {
if (G->vexs[i] == v) {
break;
}
}
//如果找不到，输出提示语句，返回-1
if (i > G->vexnum) {
printf("no such vertex.\n");
return -1;
}
return i;
}
//构造无权有向图
void CreateDG(MGraph* G) {
//输入图含有的顶点数和弧的个数
scanf("%d,%d", &(G->vexnum), &(G->arcnum));
//依次输入顶点本身的数据
for (int i = 0; i < G->vexnum; i++) {
scanf("%d", &(G->vexs[i]));
}
//初始化二维矩阵，全部归0，指针指向NULL
for (int i = 0; i < G->vexnum; i++) {
for (int j = 0; j < G->vexnum; j++) {
G->arcs[i][j].adj = 0;
G->arcs[i][j].info = NULL;
}
}
//在二维数组中添加弧的数据
for (int i = 0; i < G->arcnum; i++) {
int v1, v2;
//输入弧头和弧尾
scanf("%d %d", &v1,&v2);
//确定顶点位置
int n = LocateVex(G, v1);
int m = LocateVex(G, v2);
//排除错误数据
if (m == -1 || n == -1) {
printf("no this vertex\n");
return;
}
//将正确的弧的数据加入二维数组
G->arcs[n][m].adj = 1;
}
}
//构造无权无向图
void CreateDN(MGraph* G) {
scanf("%d %d", &(G->vexnum), &(G->arcnum));
for (int i = 0; i < G->vexnum; i++) {
scanf("%d", &(G->vexs[i]));
}
for (int i = 0; i < G->vexnum; i++) {
for (int j = 0; j < G->vexnum; j++) {
G->arcs[i][j].adj = 0;
G->arcs[i][j].info = NULL;
}
}
for (int i = 0; i < G->arcnum; i++) {
int v1, v2;
scanf("%d,%d", &v1, &v2);
int n = LocateVex(G, v1);
int m = LocateVex(G, v2);
if (m == -1 || n == -1) {
printf("no this vertex\n");
return;
}
G->arcs[n][m].adj = 1;
G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称
}
}
//构造有权有向网
void CreateUDG(MGraph* G) {
scanf("%d %d", &(G->vexnum), &(G->arcnum));
for (int i = 0; i < G->vexnum; i++) {
scanf("%d",&(G->vexs[i]));
}
for (int i = 0; i < G->vexnum; i++) {
for (int j = 0; j < G->vexnum; j++) {
G->arcs[i][j].adj = 0;
G->arcs[i][j].info = NULL;
}
}
for (int i = 0; i < G->arcnum; i++) {
int v1, v2, w;
scanf("%d %d %d", &v1, &v2, &w);
int n = LocateVex(G, v1);
int m = LocateVex(G, v2);
if (m == -1 || n == -1) {
printf("no this vertex\n");
return;
}
G->arcs[n][m].adj = w;
}
}
//构造有权无向网
void CreateUDN(MGraph* G) {
scanf("%d %d", &(G->vexnum), &(G->arcnum));
for (int i = 0; i < G->vexnum; i++) {
scanf("%d", &(G->vexs[i]));
}
for (int i = 0; i < G->vexnum; i++) {
for (int j = 0; j < G->vexnum; j++) {
G->arcs[i][j].adj = 0;
G->arcs[i][j].info = NULL;
}
}
for (int i = 0; i < G->arcnum; i++) {
int v1, v2, w;
scanf("%d %d %d", &v1, &v2, &w);
int m = LocateVex(G, v1);
int n = LocateVex(G, v2);
if (m == -1 || n == -1) {
printf("no this vertex\n");
return;
}
G->arcs[n][m].adj = w;
G->arcs[m][n].adj = w;//矩阵对称
}
}
void CreateGraph(MGraph* G) {
//选择图的类型
scanf("%d", &(G->kind));
//根据所选类型，调用不同的函数实现构造图的功能
switch (G->kind)
{
case DG:
return CreateDG(G);
break;
case DN:
return CreateDN(G);
break;
case UDG:
return CreateUDG(G);
break;
case UDN:
return CreateUDN(G);
break;
default:
break;
}
}
//输出函数
void PrintGrapth(MGraph G)
{
for (int i = 0; i < G.vexnum; i++)
{
for (int j = 0; j < G.vexnum; j++)
{
printf("%d ", G.arcs[i][j].adj);
}
printf("\n");
}
}
int main()
{
MGraph G;//建立一个图的变量，对象
CreateGraph(&G);//调用创建函数，传入地址参数，进行初始化
PrintGrapth(G); //输出图的二阶矩阵
return 0;
}
- 例如，使用上述程序存储下图 （a）的有向网时，存储的两个数组如下图 （b）所示：
//输入下列数据：
2
6 10
1
2
3
4
5
6
1 2 5
2 3 4
3 1 8
1 4 7
4 3 5
3 6 9
6 1 3
4 6 6
6 5 1
5 4 5
【 2. 图的链式存储结构 】
- 通常，图更多的是采用链表存储，具体的存储方法有 3 种，分别是邻接表、邻接多重表和十字链表。
2.1 图的临接表存储结构
2.1.1 临接表的 基本原理
- 如果图中的两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为 邻接点 。 邻接 指的是图中顶点之间有边或者弧的存在。邻接表 可用于存储 无向图 和 有向图 。
- 邻接表的实现方式：
- 给图中的各个顶点独自建立一个链表，用 首元节点存储该顶点，用链表中 其他节点存储各自的临接点。
- 同时，为了便于管理这些链表，通常会将所有 链表的头节点存储到数组中（也可以用链表存储）， 各链表在存储顶点的临接点时，仅需存储该邻接点位于数组中的下标 即可。
- 例如，存储下图 a 所示的有向图，其对应的邻接表如下图 b 所示：
以顶点 V1 为例，与其相关的邻接点分别为 V2 和 V3，因此存储 V1 的链表中存储的是 V2 和 V3 在数组中的位置下标 1 和 2。
- 对于具有 n 个顶点和 e 条边的无向图，邻接表中需要存储 n 个头结点和 2e 个链表中的结点。在图中边或者弧稀疏的时候，使用邻接表（所有链表中的节点总数为 n + 2 e n+2e n+2e）要比图的顺序存储结构中的邻接矩阵（数组大小为 n 2 n^2 n2） 更加节省空间。
2.1.2 临接表的 链表节点
- 存储各顶点的节点结构分为两部分，数据域和指针域。data 数据域用于存储顶点数据信息，next 指针域用于指向下一个临接点，如下图所示：
- 在实际应用中，除了上图这种节点结构外，对于用临接表存储网（边或弧存在权）结构，还需要节点存储权的值，因此需使用下图中的节点结构：adjvex为邻接点在数组中的下标，next指针指向下一个节点，info 表示 adjvex 所代表的顶点与临接表表头所代表顶点的权值。
2.1.3 邻接表 各结构体的C实现
- 邻接表 各结构体的 C 实现：
#define MAX_VERTEX_NUM 20 //顶点的最大个数
#define VertexType int //顶点的数据类型
#define InfoType int //弧或者边包含的信息的类型
//各顶点的临接点结构体
typedef struct ArcNode{
int adjvex;//邻接点在数组中的下标
struct ArcNode * nextarc;//指向下一个邻接点
InfoType * info;//信息域
}ArcNode;
//图的顶点结构体
typedef struct VNode{
VertexType data; //顶点的数据域
ArcNode * firstarc;//指向邻接点的指针
}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组
//图结构体
typedef struct {
AdjList vertices; //图中顶点的数组
int vexnum,arcnum; //图中顶点数和边/弧数
int kind; //图的种类
}ALGraph;
2.1.4 临接表 计算顶点的出度和入度
邻接表计算 无向图的出度和入度
- 使用邻接表 计算 无向图 中顶点的入度和出度只需从数组中 找到该顶点然后统计此链表中节点的数量 即可。
邻接表计算 有向图的出度和入度
- 使用 邻接表存储 有向图 时，通常各个顶点的链表中存储的都是以该顶点为弧尾的邻接点，因此 通过统计各顶点链表中的节点数量， 只能计算出该顶点的出度，而无法计算该顶点的入度 。
- 对于利用邻接表求某顶点的入度，有两种方式：
① 遍历整个邻接表中的节点，统计除了该顶点外所有的链表中与该顶点所在数组位置下标相同的节点数量，即为该顶点的入度；
② 建立一个 逆邻接表，该表中的各顶点链表专门用于存储以此顶点为弧头的所有顶点在数组中的位置下标。
比如说，建立一张2.1.1中图 a 对应的逆邻接表，如下图所示：
以 V1 为例，其他顶点中能到达 V1 的顶点为V4，故 顶点V1的链表中第二个节点存储的是 V4 所在数组的下标3。
2.2 图的十字链表存储结构
2.2.1 十字链表的 基本原理
- 十字链表法 仅适用于 存储有向的，即 有向图 和 有向网。不仅如此，十字链表法还 解决了邻接表不方便计算有向图顶点入度的问题。
- 十字链表存储有向图（网）的方式与邻接表有一些相同，都 以图（网）中各顶点为首元节点 建立多条链表，同时为了便于管理，还将所有链表的首元节点存储到同一数组（或链表）中。
- 十字链表实质上就是为每个顶点建立两个链表，分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点 。对于各个链表中节点来说，由于表示的都是该顶点的出度或者入度，因此 十字链表中的节点没有先后次序之分。
2.2.2 十字链表的 链表节点
- 十字链表中用于存储顶点的 顶点结构体 节点如下图所示：
- data ：用于存储该顶点中的数据；
- firstin 指针：用于连接以当前顶点为弧头的其他顶点构成的链表；
- firstout 指针：用于连接以当前顶点为弧尾的其他顶点构成的链表；
- 十字链表中 弧结构体 节点如下图所示：
- tailvex： 存储该弧弧尾的顶点位于数组中的下标；
- headvex：存储该弧弧头的顶点位于数组中的下标；
- hlink 指针：指向下一个与该弧弧头相同的弧的节点；
- tlink 指针：指向下一个与该弧弧尾相同的弧的节点；
- info 指针（可选）：用于存储与该顶点相关的信息，例如两顶点之间的权值；
- 例如，用十字链表存储下图 a 中的有向图，存储状态如下图 b 所示：
- 以顶点 V1 为例，以 V1 为弧头的弧只有 V4→V1。因此，V1 的 firstin 指针指向 V4→V1 这条弧，而在 剩下的弧中没有与 V4→V1 这条弧弧头相同的节点，故 V4→V1 这条弧的 hlink 指针指向空。如图中红色颜色所示。
- 同样，以 V1 为弧尾的弧有 V1→V2 和 V1→V3（不区分先后次序）这两条弧。因此，V1 的 firstout 指针指向 V1→V2 这条弧的节点， V1→V2 这条弧的 tlink 指针指向 V1→V3 这条弧， V1→V3 这条弧的 tlink 指针指向空。如图中棕色颜色所示。
2.2.3 十字链表的 C实现
#define MAX_VERTEX_NUM 20
#define InfoType int//图中弧包含信息的数据类型
#define VertexType int
//链表中的其他节点结构体
typedef struct ArcBox
{
int tailvex, headvex;//弧尾、弧头对应顶点在数组中的位置下标
struct ArcBox* hlik, * tlink;//分别指向弧头相同和弧尾相同的下一个弧
InfoType* info;//存储弧相关信息的指针
}ArcBox;
//链表的首元节点结构体
typedef struct VexNode
{
VertexType data;//顶点的数据域
ArcBox* firstin, * firstout;//指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;
//图结构体
typedef struct
{
VexNode xlist[MAX_VERTEX_NUM];//存储顶点的一维数组
int vexnum, arcnum;//记录图的顶点数和弧数
}OLGraph;
int LocateVex(OLGraph* G, VertexType v)
{
int i = 0;
//遍历一维数组，找到变量v
for (; i < G->vexnum; i++) {
if (G->xlist[i].data == v) {
break;
}
}
//如果找不到，输出提示语句，返回 -1
if (i >= G->vexnum) {
printf("no such vertex.\n");
return -1;
}
return i;
}
//构建十字链表函数
void CreateDG(OLGraph* G) {
//输入有向图的顶点数和弧数
scanf("%d,%d", &(G->vexnum), &(G->arcnum));
//使用一维数组存储各顶点数据，初始化指针域为NULL
for (int i = 0; i < G->vexnum; i++) {
scanf("%d", &(G->xlist[i].data));
G->xlist[i].firstin = NULL;
G->xlist[i].firstout = NULL;
}
//构建十字链表
for (int k = 0; k < G->arcnum; k++) {
int v1, v2;
scanf("%d,%d", &v1, &v2);
//确定v1、v2在数组中的位置下标
int i = LocateVex(G, v1); //弧的尾的下标
int j = LocateVex(G, v2); //弧的头的下标 i→j
//建立弧的其他节点
ArcBox* p = (ArcBox*)malloc(sizeof(ArcBox));
p->tailvex = i;
p->headvex = j;
//采用头插法插入新的p结点
p->tlink = G->xlist[i].firstout;
p->hlik = G->xlist[j].firstin;
G->xlist[j].firstin = G->xlist[i].firstout = p;
}
}
2.3 图的临接多重表存储结构
2.3.1 临接多重表的 基本原理
- 问题背景
无向图的存储可以使用邻接表，但在实际使用时，如果想对图中某顶点进行实操（修改或删除），由于邻接表中存储该顶点的节点有两个，因此需要操作两个节点。
而无向图的另一种存储结构—— 邻接多重表 可以提高无向图中操作顶点的效率。 - 邻接多重表 仅适用于 存储无向的，即无向图或无向网。
- 邻接多重表存储无向图的方式，可看作是邻接表和十字链表的结合。同邻接表和十字链表存储图的方法相同，都是独自为图中各顶点建立一张链表，存储各顶点的节点作为各链表的首元节点，同时为了便于管理将各个首元节点存储到一个数组中。
2.3.2 临接多重表的 链表节点
- 邻接多重表采用与邻接表相同的首元节点结构， 顶点结构体 节点 如下图所示：
- data：存储此顶点的数据；
- firstedge：指针域，指向同该顶点有直接关联的存储其他顶点的节点。
- 临接多重表的各链表中 边结构体 节点如下图所示：
- mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历；
- ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的下标；
- ilink：指针域，指向下一个以 ivex 为顶点的边结构体；
- jlink：指针域，指向下一个以 jvex 为顶点的边结构体；
- info：指针域，用于存储与该顶点有关的其他信息，比如无向网中各边的权；
- 如果我们想使用邻接多重表存储下图 a 中的无向图，则与之对应的邻接多重表如下图 b 所示：
- 以顶点 V1 为例，以 V1 为顶点的边有 V1-V2 和 V1-V4（不区分先后次序）这两条边。因此，V1 的 firstedge 指针指向 V1-V2 这条边的节点， V1-V2 这条边的 ilink 指针指向 V1-V4 这条边的节点， V1-V4 这条边的 ilink 指针指向空。如图中棕色颜色所示。
2.3.3 临接多重表的 C 实现
#define MAX_VERTEX_NUM 20 //图中顶点的最大个数
#define VertexType int //图顶点的数据类型
#define InfoType int //边含有的信息域的数据类型
typedef enum { unvisited, visited }VisitIf; //边标志域
//边结构体
typedef struct EBox {
VisitIf mark; //标志域
int ivex, jvex; //边的两个顶点在数组中的位置下标
struct EBox* ilink, * jlink; //分别指向与ivex、jvex相关的下一个边
InfoType* info; //边包含的其它的信息域的指针
}EBox;
//顶点的首元节点结构体
typedef struct VexBox {
VertexType data; //顶点数据域
EBox* firstedge; //顶点相关的第一条边的指针域
}VexBox;
//图结构体
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM]; //图中顶点的数组
int vexnum, degenum; //图中顶点的个数和边的个数
}AMLGraph;
【 3. 图的各存储结构的对比 】
| 图的存储结构 | 可存储的图的类型 | 核心实现 | 优点 | 缺点 |
|---|---|---|---|---|
| 数组 | 有向、无向 | 一维数组存储顶点数据，二维数组存储各顶点间的关系。 | \ | \ |
| 临接表 | 有向、无向 | 一维数组存储各顶点的结构体（顶点结构体存储该顶点的数据和指向该顶点临接点结构体的指针）； 临接点结构体中包括该临接点的数据下标和指向下一个临接点结构体的指针。 | \ | 不方便计算有向图中顶点的入度； 不方便操作无向图的顶点 |
| 十字链表 | 有向 | 一维数组存储各顶点的结构体（顶点结构体存储各顶点的数据和两个分别指向以该顶点为弧头和弧尾的弧结构体的指针）； 弧结构体中存储该弧弧头和弧尾的数据下标、两个分别指向下一个与该弧弧头或弧尾相同的弧的弧结构体。 | 解决了邻接表不方便计算有向图顶点入度的问题。 | 不能存储无向的 |
| 临接多重表 | 无向 | 一维数组存储各顶点的结构体（顶点结构体存储各顶点的数据和指向以该顶点为端点的边结构体的指针）； 边结构体存储该边是否被操作过的标记位、该边两个顶点的数据下标、两个分别指向下一个与该边顶点相同的边结构体。 | 解决了临接表不方便操作无向图顶点的问题。 | 不能存储有向的 |
