【数据结构】图的基本概念，图的存储结构（邻接矩阵；邻接表；十字链表；邻接多重表）

欢~迎~光~临~^_^

1、图的基本概念

2、图的存储结构

2.1邻接矩阵

2.2邻接表

2.3十字链表

2.4邻接多重表

2.5图的四种存储结构的对比

1、图的基本概念

图是由一组节点（通常称为顶点）和一组连接这些节点的边（通常称为边）组成的数据结构。图可以用于表示各种实际问题，如网络拓扑、道路系统、社交网络和电路等。

以下是图的一些基本概念：

顶点（Vertex）：图中的节点。
边（Edge）：图中连接顶点的线段。
有向图（Directed Graph）：每条边都有一个指向性，即从一个顶点到另一个顶点的方向只能是一个方向。全部顶点的入度之和与出度之和相等。顶点的度等于其入度和出度之和。
无向图（Undirected Graph）：边没有指向性，从一个顶点到另一个顶点的方向没有限制。全部顶点的度的和等于边的2倍。
边权（Edge Weight）：边上附加的一个数值，代表两个顶点之间的距离或者权值。
度（Degree）：一个顶点的度是指与该顶点相连的边的数目。在有向图中，度被分为入度和出度。
路径（Path）：在图中，路径是通过边从一个顶点到另一个顶点的一系列顶点。
周长（Cycle）：一个简单图中，如果从一个顶点出发经过若干边回到该顶点，称这个路径为周长。
连通图（Connected Graph）：如果一个无向图中的任意两个顶点都可以通过一些边相连到达，则称该图为连通图。
强联通图（Strongly Connected Graph）：对于有向图而言，如果任意两个顶点之间都存在双向路径，则称该图为强联通图。
带权图（Weighted Graph）：图中的边带有权值或者距离。
子图（Subgraph）：在一个图中取出一部分顶点和边所组成的图。
简单路径：顶点不重复出现的路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
连通分量：无向图中的极大连通子图。
强连通分量：有向图中的极大连通子图。
无向完全图：有n(n-1)/2条边。
有向完全图：有n(n-1)条边。

常见考点：

2、图的存储结构

2.1邻接矩阵

邻接矩阵用一个二维数组来表示图中各个顶点之间的连通关系。邻接矩阵A的大小为nxn，其中A[i][j]表示节点i到节点j是否存在边，如果存在则为1，否则为0。

邻接矩阵的定义如下：

设 G=(V,E) 是一个无向图，其中 V={v1,v2,...,vn} 为顶点集合，E 为边集合。邻接矩阵 A 是一个 n×n 的矩阵，其中 A(i,j)=1 表示 vi 和 vj 之间有一条边，A(i,j)=0 表示 vi 和 vj 之间没有边。

对于有向图，邻接矩阵的定义稍有不同，具体如下：

设 G=(V,E) 是一个有向图，其中 V={v1,v2,...,vn} 为顶点集合，E 为边集合。邻接矩阵 A 是一个 n×n 的矩阵，其中 A(i,j)=1 表示存在一条从 vi 到 vj 的有向边，A(i,j)=0 表示不存在这样的有向边。

在C语言中，我们可以使用二维数组来实现邻接矩阵存储结构，结构定义如下：

#define MAX_VERTEX_NUM 100  // 定义图中顶点最大数量typedef struct {int vertex[MAX_VERTEX_NUM];  // 存储顶点信息int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 存储边信息int vertexNum;  // 实际顶点数量int edgeNum;  // 实际边数量
} GraphMatrix;

其中，`vertex`数组存储图中所有顶点的信息，`edge`数组存储边的信息，`vertexNum`和`edgeNum`分别表示实际顶点和边的数量。

注意，使用邻接矩阵存储大型图时，可能会遇到空间限制的问题，因此需要针对具体情况酌情调整顶点数量的上限。

2.2邻接表

图的邻接表是一种表示无向图或有向图的数据结构。它将每个顶点与与之相邻的顶点列表关联起来，其中每个顶点的邻居顶点列表都存储在该顶点对应的链表中。

例如，下面是一个无向图的邻接表表示：

0: 1 -> 2 -> 3
1: 0 -> 2
2: 0 -> 1 -> 3
3: 0 -> 2

其中，每行表示一个顶点和它的邻居顶点列表。例如，第一行表示顶点0和它的邻居顶点1、2、3。

在有向图的邻接表表示中，每个顶点的邻居顶点列表存储的是它的出边或入边，具体取决于是表示出度还是入度。

邻接表适合表示稀疏图，因为它只存储了每个顶点的度数大小的信息，而对于度数较小的顶点，它所对应的链表长度也比较短。

C语言，图的邻接表存储结构定义如下：

#define MAX_VERTEX_NUM 20 // 图中顶点的最大个数// 边表结点
typedef struct ArcNode {int adjvex;             // 该弧所指向的顶点的位置struct ArcNode *next;   // 指向下一条弧的指针// 如果需要存储边的权值，可以在此处添加一个 weight 变量
} ArcNode;// 顶点表结点
typedef struct VNode {char data;              // 顶点信息ArcNode *first;         // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];// 图
typedef struct {AdjList vertices;       // 邻接表int vexnum, arcnum;     // 图的顶点数和弧数
} ALGraph;

在邻接表中，每个顶点都由一个顶点表结点表示，其中 data 为顶点信息，first 指向第一条依附该顶点的弧的指针。每个弧都由一个边表结点表示，其中 adjvex 指向该弧所指向的顶点在顶点表中的位置，next 指向下一条依附该顶点的弧的指针。同时，邻接表以一个包含图中所有顶点的顶点表结点数组表示。

2.3十字链表

图的十字链表是一种存储有向图的方式，它使用链表来表示图中的节点和边。它的特点是每个节点维护四个指针，分别指向它的出边、入边、右边和下边。这样，我们可以快速访问每个节点的邻居节点和以该节点为起点或终点的边。

具体来说，每个节点维护四个指针：

1. 出边指针：指向以该节点为起点的第一条边。

2. 入边指针：指向以该节点为终点的第一条边。

3. 右边指针：指向与该节点在同一层级的下一个节点。

4. 下边指针：指向与该节点在下一层级的相邻节点，通常用于存储节点的入度信息。

这种存储方式在图的遍历和其他算法中具有很好的效率，尤其是对稀疏图而言。因此，在实际应用中，十字链表常被用于表示稀疏图和网络。

C语言，图的十字链表存储结构的定义：

#define MAX_VERTEX_NUM 20 // 最大顶点数// 边表结构体定义
typedef struct ArcNode {int tailvex; // 弧尾int headvex; // 弧头struct ArcNode* hlink; // 指向同一个弧头的下一条边struct ArcNode* tlink; // 指向同一个弧尾的下一条边// 其他信息，如权值等
} ArcNode;// 顶点表结构体定义
typedef struct VexNode {char data; // 顶点信息ArcNode* firstin; // 指向以该顶点为弧头的第一条边ArcNode* firstout; // 指向以该顶点为弧尾的第一条边
} VexNode;// 十字链表存储结构体定义
typedef struct {VexNode vexs[MAX_VERTEX_NUM]; // 顶点表int vexnum; // 当前图的顶点数int arcnum; // 当前图的边数
} OLGraph;

2.4邻接多重表

邻接多重表是一种表示无向图的数据结构，它通过将每个顶点和边都表示为一个结点，并对它们进行链表连接来存储图。

邻接多重表的结构如下：

1. 图中每个顶点都有一个结点，包含以下信息：

- data：顶点的数据元素。
- firstedge：指向与该顶点相连的第一条边的指针（即链表中的头结点）。

2. 图中每条边都有一个结点，包含以下信息：

- mark：标记此边是否被访问过。
- ivex：该边连接的另一个顶点的位置（下标）。
- ilink：指向与该顶点相连的下一条边的指针。
- jvex：该边连接的另一个顶点的位置（下标）。
- jlink：指向与该顶点相连的下一条边的指针。

邻接多重表的优点是：

- 可以快速查找一个顶点的所有邻接点和边。
- 可以快速删除一个图中的点和边。
- 占用的存储空间比邻接表和邻接矩阵更少。

邻接多重表的缺点是：

- 不方便进行图的遍历。
- 在插入一个新顶点时，需要为其分配两个结点，因此需要更多的存储空间。

C语言，图的邻接多重表存储结构的定义：

#define MAX_VERTEX_NUM 20  // 最大顶点数typedef struct ArcNode {  // 边表结点int ivex, jvex;  // 该边依附的两个顶点在顶点表中的位置struct ArcNode *ilink, *jlink;  // 分别指向依附这两个顶点的下一条边
} ArcNode;typedef struct VNode {  // 顶点表结点char data;  // 顶点信息ArcNode *firstarc;  // 指向第一条依附该顶点的边的指针
} VNode;typedef struct {  // 邻接多重表VNode vertices[MAX_VERTEX_NUM];  // 顶点表int vexnum, arcnum;  // 图的当前顶点数和边数
} AMLGraph;

该结构体定义了一个邻接多重表，其中顶点表的每个元素是一个VNode结构体，表示一个顶点。VNode结构体中包含了指向以该顶点为起点的第一条边的指针firstarc。边表结点ArcNode表示一条边，其中包含了ivex和jvex两个顶点在顶点表中的位置，以及指向依附这两个顶点的下一条边的指针ilink和jlink。