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

  欢~迎~光~临~^_^

目录

1、图的基本概念

2、图的存储结构

2.1邻接矩阵

2.2邻接表 

2.3十字链表

2.4邻接多重表 

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

---

1、图的基本概念

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

以下是图的一些基本概念

1. 顶点Vertex图中的节点。

2. 边Edge图中连接顶点的线段。

3. 有向图Directed Graph每条边都有一个指向性即从一个顶点到另一个顶点的方向只能是一个方向。全部顶点的入度之和与出度之和相等。顶点的度等于其入度和出度之和。

4. 无向图Undirected Graph边没有指向性从一个顶点到另一个顶点的方向没有限制。全部顶点的度的和等于边的2倍。

5. 边权Edge Weight边上附加的一个数值代表两个顶点之间的距离或者权值。

6. 度Degree一个顶点的度是指与该顶点相连的边的数目。在有向图中度被分为入度和出度。

7. 路径Path在图中路径是通过边从一个顶点到另一个顶点的一系列顶点。

8. 周长Cycle一个简单图中如果从一个顶点出发经过若干边回到该顶点称这个路径为周长。

9. 连通图Connected Graph如果一个无向图中的任意两个顶点都可以通过一些边相连到达则称该图为连通图。

10. 强联通图Strongly Connected Graph对于有向图而言如果任意两个顶点之间都存在双向路径则称该图为强联通图。

11. 带权图Weighted Graph图中的边带有权值或者距离。

12. 子图Subgraph在一个图中取出一部分顶点和边所组成的图。

13. 简单路径顶点不重复出现的路径。

14. 简单回路除第一个顶点和最后一个顶点外其余顶点不重复出现的回路。

15. 连通分量无向图中的极大连通子图。

16. 强连通分量有向图中的极大连通子图。

17. 无向完全图有n(n-1)/2条边。

18. 有向完全图有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。

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

 

❤️❤️❤️图的知识点总结就到这里啦如果对博文还满意的话劳烦各位大佬儿动动“发财的小手”留下您对博文的赞和对博主的关注吧❤️❤️❤️