定义

真题练习：可在站内题库按“图的概念”知识点筛选。

树和图的定义是后续应用的基础，需牢固掌握 图的概念以及邻接矩阵和邻接表这两种 存储方式。

图的概念

图是由顶点和边组成的非线性数据结构。顶点有时也被称为节点，而边是连接图中任意两个节点的线或弧。更正式地说，图由顶点集合 $V$ 与边集合 $E$ 组成，记作

G=(V,E).

补充

树和图的区别？

树是受限制的图类型，只是有更多的规则。每棵树都是一个图，但不是所有的图都是树。链表、树和堆都是图的特殊情况。

在图论中，根据边的方向性、连接方式、顶点间的关系等，可以进一步划分出多种类型的图，并引入如 连通性、完全性、度数等一系列关键概念。这些分类和术语有助于我们更好地理解图的结构特点和应用场景，下面我们将逐一进行介绍。

方向

有向图（directed graph）：边是有方向的，从一个定点指向另一个定点
无向图（undirected graph）：边是没有方向的

连通性

连通图（Connected Graph）：图中的每一对不同顶点都可以通过一条或多条边相互连接，也就是说，从图中的任意一个顶点出发，都可以到达图中的任意其他顶点。
非连通图（Disconnected Graph）：图中存在两个或多个互不相连的子图，也就是说，其中至少存在一个顶点集合，无法通过边连接到图中的其他顶点集合。
完全图（Complete Graph）：完全图是一种特殊的图，其中每一对不同的顶点都直接相连，也就是说，完全图中的任意两个顶点之间都存在一条边。如果一个无向完全图有 $n$ 个顶点，那么边数为
$\binom{n}{2}=\frac{n(n-1)}{2},$
其中 $\binom{n}{2}$ 表示从 $n$ 个顶点中选择 2 个顶点的组合数。

连通分量（Connected Components）：也称为连通子图，是一个无向图中的一个重要概念。一个连通分量是指在无向图中，如果从其中一个顶点出发，可以通过边的路径到达该连通分量内的任何其他顶点，而无法通过图中的边到达其他连通分量内的顶点。

度

顶点的度（Degree）：无向图中，顶点的度是与该顶点关联的边数；有向图中，顶点的度等于入度与出度之和。
- 在无向图中，顶点的度就是与该顶点相邻的边的数量。
- 在有向图中，若顶点 $v$ 的入度为 $d^-(v)$ 、出度为 $d^+(v)$ ，则
  $d(v)=d^-(v)+d^+(v).$
入度（In-Degree）：入度是指在有向图中指向某个顶点的边的数量，也就是与该顶点关联的边中以该顶点为终点的边的数量。
出度（Out-Degree）：出度是指在有向图中从某个顶点出发的边的数量，也就是与该顶点关联的边中以该顶点为起点的边的数量。

路径

简单路径：顶点不出现重复的路径
非简单路径：顶点出现重复的路径
回路：路径的起点和终点相同

图的存储

在我们使用数据结构存储图时，主要关注两点：1. 如何存储顶点？2. 如何存储边？采用的数据结构需要能够准备表示这些信息。

邻接矩阵

定义

图的 邻接矩阵（Adjacency Matrix）是一种常用的图表示方法，特别适用于 稠密图，它以矩阵的形式表示图的连接关系。

在邻接矩阵中，行和列分别代表 图的顶点，矩阵的元素表示顶点之间是否相邻或者 边的权重。

对于 无向图：
- 如果顶点 i 和顶点 j 之间存在边，则邻接矩阵中 (i,j) 和 (j,i) 位置的元素都被标记为 1 （或者表示边的权重）。
- 如果顶点 i 和顶点 j 之间不存在边，则邻接矩阵中 (i,j) 和 (j,i) 位置的元素都被标记为 0 。
对于 有向图：
- 如果有一条从顶点 i 到顶点 j 的有向边，则邻接矩阵中 (i,j) 位置的元素被标记为 1 （或者表示边的权重）。
- 如果没有从顶点 i 到顶点 j 的有向边，则邻接矩阵中 (i,j) 位置的元素被标记为 0 。

实现

在邻接矩阵的实现中，我们使用一个 二维数组 来表示图的连接关系，邻接矩阵matrix 的行数和列数与图中的顶点数量相同。其中 matrix[i][j] 表示顶点i 到顶点j 是否有边（或边的权值）。

邻接矩阵定义
添加边

#define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵

// 初始化邻接矩阵
void initializeMatrix(int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0; // 初始化所有元素为 0
        }
    }
}

// 在邻接矩阵中添加一条边
void addEdge(int start, int end) {
    adjMatrix[start][end] = 1; // 添加边，将对应位置的元素设为 1
    adjMatrix[end][start] = 1; // 无向图需要将对称位置的元素也设为 1
}

入度与出度

如果需要计算 邻接矩阵 中某个顶点的出度的话，假设顶点编号为 i，我们统计 邻接矩阵 中的 第 i 行 有多少元素不为 0 即可（该顶点指向哪些顶点）。

如果需要计算 邻接矩阵 中某个顶点的入度的话，假设顶点编号为 i，我们统计 邻接矩阵 中的 第 i 列 有多少元素不为 0 即可（哪些顶点指向该顶点）。

邻接表

定义

图的 邻接表（Adjacency List）是一种常见的图表示方法，特别适用于 稀疏图，它使用链表或数组的形式来表示图的连接关系。每个顶点都对应一个链表，链表中存储与该顶点相邻的其他顶点。

邻接表的主要思想是为 每个顶点创建一个链表，链表中的每个节点表示与该顶点相邻的另一个顶点。对于无向图，通常需要为每一条边创建两个链表节点，分别表示两个相邻的顶点。

实现

在邻接表的实现中，我们为每个顶点维护一个链表，用于存储与该顶点相邻的所有顶点；所有顶点对应的 链表头节点 组成一个数组或列表（在以下实现为 struct AdjList *array），形成整个图的邻接表结构。

数据结构
创建新节点
创建图
添加边

// 链表节点结构：表示邻接的一个顶点
struct Node {
    int dest;            // 邻接顶点的编号
    struct Node* next;   // 指向下一个邻接点
};

// 邻接表：每个顶点有一个链表
struct AdjList {
    struct Node* head;   // 链表头
};

// 图结构
struct Graph {
    int V;                      // 顶点数
    struct AdjList* array;      // 邻接表数组
};

struct Node* newNode(int dest) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->dest = dest;
    node->next = NULL;
    return node;
}

struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;

    // 创建邻接表数组
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    // src -> dest
    struct Node* n1 = newNode(dest);
    n1->next = graph->array[src].head;
    graph->array[src].head = n1;

    // dest -> src（因为是无向图）
    struct Node* n2 = newNode(src);
    n2->next = graph->array[dest].head;
    graph->array[dest].head = n2;
}

邻接多重表

邻接多重表（Adjacency Multi-list）是一种用于表示 无向图 的数据结构，主要用于避免在 邻接表 存储方式中重复存储 无向边，提高存储效率，同时便于图的操作（如边的删除）。

邻接多重表中顶点种类 分为两种：

顶点结点（Vertex Node）：
- 每个顶点有一个头结点，存储该顶点的信息，以及指向其所有关联边的指针。
边结点（Edge Node）：
- 每条边有一个结点，存储该边的两个顶点及其相关信息。
- 该结点包含两个指针，分别指向该边所连接的两个顶点的邻接边链表的下一条边，使得图的存储更加紧凑。

还是举个实际例子说明，在上述的邻接多重表中，总共需要存储 5 条边，每条边只需要存储一次，所以总共有 5 个边结点，每个边结点中存储的数据如下表所示：

边	`ivex`	`jvex`	`ilink` 指向	`jlink` 指向
12	1	2	13	23
13	1	3	14	32
14	1	4	`NULL`	43
23	2	3	`NULL`	34
34	3	4	`NULL`	`NULL`

注意

ilink 和 jlink 的含义是什么？

ilink 和 jlink 指向的是“该边对应顶点的下一条边”，用于遍历一个顶点的所有相邻边。这样，每条 无向边 只存储一次，同时仍然能通过 ilink 和 jlink 遍历所有邻接的边。

总结一下，相比于邻接表，邻接多重表最大的不同在于如下两点：

节省存储空间：对于无向图，每条边只存储一次。
方便进行边的操作：例如，删除一条边时，只需要修改相关顶点的链表中的指针，而不需要像邻接表那样在两个顶点的邻接表中都进行操作。

十字链表

十字链表（Orthogonal List）是一种用于表示 有向图 的链式存储结构，它兼顾了出边和入边的高效查找。相比 邻接表 只方便查找出边，十字链表 允许同时高效遍历某个顶点的所有出边和所有入边。

在 十字链表（Orthogonal List）中，顶点种类也可以分为两种：

顶点结点：
- 每个顶点对应一个头结点，存储该顶点的信息；
- 同时包含两个指针：
  - firstout：指向从该顶点出发的第一条出边；
  - firstin：指向以该顶点为终点的第一条入边；
- 这样可分别建立“出边链表”和“入边链表”。
边结点：
- 每条有向边对应一个边结点，存储该边的起点和终点在顶点表中的位置；
- 包含两个指针，使该边同时链接在：
  - 起点顶点的出边链表中（通过 hlink）；
  - 终点顶点的入边链表中（通过 tlink）；
- 边结点也可扩展存储额外信息（如权重）。

下图给出了一个 十字链表 的一个实例，其中忽略了 边结点 的 info 字段。我们可以沿着 顶点结点 的 firstin 和 firstout 字段高效遍历所有的入边和出边。

图的数量关系与存储结构选择

简单图不含自环，也不含同一对顶点之间的重边；多重图允许重边，自环是否允许则须看题设。无向图中一条普通边同时连接两个端点，所以所有顶点度数之和满足

\sum_{v\in V}\deg(v)=2|E|.

若允许无向自环，同一个环在同一顶点提供两个关联端，因此对该顶点的度贡献为 2。对于有向图，每条弧恰好贡献一个出度和一个入度，故

\sum_{v\in V}\operatorname{outdeg}(v) =\sum_{v\in V}\operatorname{indeg}(v)=|E|.

这些式子用于检查图示或邻接表是否漏边很有效：无向图度数和必须为偶数；有向图入度和、出度和必须相同。

连通性的限定词

无向图中，任意两顶点之间存在路径称为连通；极大连通子图称为连通分量。有向图必须区分：任意两顶点彼此都可达才是强连通；把边方向忽略后连通只叫弱连通。一张图可以弱连通却不是强连通，例如只有一条 $A\to B$ 的有向边。不能把“从某个源点能走到所有顶点”误当成任意两点强连通。

用操作需求反推存储结构

设图有 $n$ 个顶点、 $e$ 条边。邻接矩阵用 $n^2$ 个单元，无论图是否稀疏都占 $O(n^2)$ 空间；检查一条指定边是否存在可直接访问矩阵单元，时间为 $O(1)$ ，扫描某个顶点的所有邻接点则要看完整行或列，为 $O(n)$ 。邻接表只为实际边建立表结点，空间为 $O(n+e)$ ，遍历一个顶点的出边为 $O(\operatorname{outdeg}(v))$ ，但判断指定边是否存在要扫描该表，最坏为 $O(\operatorname{outdeg}(v))$ 。

需求	更合适的结构	原因
稠密图或频繁查询某对顶点是否相邻	邻接矩阵	直接按行列定位边
稀疏图、遍历和 DFS/BFS	邻接表	不为不存在的边分配空间
无向图且频繁删除一条边	邻接多重表	同一条边只存一次，两个端点的链接同时可定位
有向图且同时频繁查入边和出边	十字链表	顶点同时维护第一入边与第一出边

带权图的邻接矩阵中，不能用 0 同时表示“无边”和“权重为 0 的边”；通常用 $\infty$ 或题目约定的特殊值表示不可达，并令主对角线为 0。邻接表若存储有向图，表结点的方向是从表头顶点指向邻接顶点；无向图每条边通常在两个顶点的表中各出现一次，因此表结点总数为 $2e$ ，这一点也常用于空间或度数题。