图的定义

🔥 高优先级

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

图的概念

图是由顶点和边组成的非线性数据结构。顶点有时也被称为节点，而边是连接图中任意两个节点的线或弧。更正式地说，图是由一组顶点 (V) 和一组边 (E) 组成的。图用 G(V,E) 表示。

补充

树和图的区别？

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

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

基础性质（6.1）

无向图有 n 个顶点和 n 条边时必含环；无向森林在 n 个顶点上最多只有 n−1 条边。

从无向图任意顶点进行一次 DFS 能访问全部顶点，当且仅当图连通。

连通分量是无向图的极大连通子图；子图的每条边端点都必须属于所选顶点集。

简单无向图 n 个顶点的边数上界为 n(n−1)/2；28 条边的非连通图至少需要 9 个顶点（8 点完全图加孤立点）。

计数、连通与生成树（6.1）

连通无向图的最少边数为 n−1，可由一棵生成树达到；强连通有向图的最少边数为 n，可由包含全部顶点的有向环达到。

无向图满足握手定理：(\sum_{v\in V}\deg(v)=2|E|)。先求度数总和，再按已知度数扣除，才能反推顶点数。

简单有向图中任一顶点的入度、出度分别至多为 n−1，因此总度至多为 2n−2。

n 个顶点的无向图若有至少 (\binom{n-1}{2}+1) 条边则必连通；最密的不连通构造是 (K_{n-1}) 加一个孤立点。
这个“保证连通”阈值来自最密的不连通构造，而不是连通图的最少边数：7 个顶点时，(K_6) 加孤立点有 15 条边仍不连通，故至少 16 条边才必连通。

生成树覆盖原图全部顶点，是无环的极小连通子图，含 n−1 条边；连通分量则是极大的连通子图，二者不能混淆。

要使连通分量数最大，可把边集中在尽量少的顶点上；例如 21 条边可构成 (K_7)，因为 (\binom{7}{2}=21)，其余顶点保持孤立。

(n) 个顶点的环有 (n) 棵生成树：删除环上任意一条边，都会得到一棵不同的生成树。

(n) 个顶点、(e) 条边的森林有 (n-e) 棵树；每个连通分量都是树，逐棵使用“边数 = 顶点数 − 1”即可推出。

无向图握手定理保证所有顶点度数之和为偶数；连通图仅保证边数至少为 (n-1)（树可取等号），且不保证存在度为 1 的顶点（环是反例）。

用握手定理反推最少顶点数时，先计算剩余度数 (2|E|-\sum d_{known})，再用“其余顶点的最大允许度数”除以剩余度数并向上取整；例如 16 条边、3 个 4 度点和 4 个 3 度点时，剩余度数为 8，其余点度至多 2，故至少需要 4 个其余顶点。

连通无向图必须满足 (|E|\ge |V|-1)。因此 (|V|>|E|+1)（即 (|E|<|V|-1)）一定不连通；反过来 (|E|\ge |V|-1) 不能单独保证连通。

方向

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

连通性

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

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

度

顶点的度 （Degree）：顶点的度是指与该顶点相邻的边的数量，也就是与该顶点直接相连的其他顶点的个数。对于有向图和无向图都适用。
在无向图中，顶点的度就是与该顶点相邻的边的数量。
在有向图中，顶点的度分为入度和出度，分别表示指向该顶点的边的数量和从该顶点出发的边的数量的总和。
- 入度（In-Degree）：入度是指在有向图中指向某个顶点的边的数量，也就是与该顶点关联的边中以该顶点为终点的边的数量。
- 出度（Out-Degree）：出度是指在有向图中从某个顶点出发的边的数量，也就是与该顶点关联的边中以该顶点为起点的边的数量。

路径

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

路径、稀疏存储与拓扑序的组合判断（6.4-34）

组合判断题要逐条判定后再映射选项：简单路径要求顶点不重复，回路却要求首尾顶点相同，所以回路不是简单路径（“简单回路”只表示除首尾外不重复）；稀疏图中 e≪n²，邻接矩阵仍占 O(n²)，邻接表只占 O(n+e)；有向图存在拓扑序当且仅当它无有向环。因此“回路是简单路径”和“稀疏图用矩阵更省空间”都错，只有“有拓扑序则无回路”正确。

图的存储

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

邻接矩阵

未压缩的邻接矩阵为 (n\times n) 的表格，空间复杂度是 (O(n^2))，只由顶点数 (n) 决定，与边数无关；只有在明确采用压缩存储时才可降低空间。

邻接表不是“只能表示有向图”：有向图可记录出边（需要时可另建逆邻接表记录入边），无向图则为每条边在两个端点的表中各放一个表项。

有向图邻接矩阵主对角线以下全为 0 时，边只能从小编号顶点指向大编号顶点，因而无环；按编号升序即可得到一个拓扑序列，但拓扑序列未必唯一。

简单图邻接矩阵主对角线全为 0、其余位置全为 1，表示任意两个不同顶点均相邻，因此是完全图；矩阵是否对称才决定能否据此判断无向性。

简单无向图的邻接矩阵共有 (n^2) 个位置，每条边贡献两个对称的非零位置，所以零元素数为 (n^2-2e)。

带权有向图邻接矩阵中，若无边记为 (\infty)、对角线为 0，则顶点 (v_i) 的入度是第 (i) 列中既非 (\infty) 又非 0 的元素个数；第 (i) 行对应出度。

固定顶点编号后，邻接矩阵的行列位置确定，表示唯一；邻接表受边输入顺序和插入位置影响，表示不唯一。

邻接矩阵幂满足 ((A^k)_{ij}) 等于从顶点 (i) 到顶点 (j) 的长度恰为 (k) 的路径数；它不是“不超过 (k)”的路径数。

邻接表空间复杂度为 (O(n+e))；无向图每条边在两个端点表中各存一次，因此边表结点数为 (2e)。

无向图邻接表的边表结点总数恒为 (2e)（偶数）；若边表结点总数为奇数，则该表示只能是有向图。

有向邻接表按起点组织出边；顶点入度需扫描所有边表，统计目标顶点为该顶点的边结点，不能只扫自身链表。

(n) 个顶点的简单无向完全图有 (n(n-1)/2) 条边，邻接表最多有 (n(n-1)) 个边表结点。

建立邻接表需初始化顶点表并处理每条边，时间复杂度为 (O(n+e))（无向边处理两次仍为线性）。

有向邻接表删除顶点 (v) 的所有相关边：删除出边后还需扫描其余边表删除入边，总时间复杂度为 (O(n+e))。

定义

图的 邻接矩阵 （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) {
```c
for (int i = 0; i < vertices; i++) {
    for (int j = 0; j < vertices; j++) {
        adjMatrix[i][j] = 0; // 初始化所有元素为 0
    }
}

}


  * 添加边

```c
TODO

入度出度

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

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

邻接表

定义

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

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

实现

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

数据结构

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

};

// 邻接表：每个顶点有一个链表 struct AdjList {

struct Node* head;   // 链表头

};

// 图结构 struct Graph {

int V;                      // 顶点数
struct AdjList* array;      // 邻接表数组

};


  * 创建新节点

TODO

  * 创建图

```c
struct Graph* createGraph(int V) {
```c
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;

}


  * 添加边

```c
```c
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;
}



    

```c
邻接多重表

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

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

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

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

ilink 和 jlink 的含义是什么？

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

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

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

十字链表

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

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

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

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

邻接表求入度的复杂度

标准邻接表按出边组织。若没有额外的逆邻接表，求某顶点入度必须扫描所有顶点的边表，时间复杂度为 O(n+e)；求出度则只需扫描该顶点的边链表。

邻接表中的度数统计

无向图邻接表中，每条边在两个端点链表各出现一次，因此顶点链表长度就是该顶点的度；有向图中链表长度直接给出出度，入度需要统计所有指向该顶点的边。

邻接多重表适用范围

邻接多重表面向无向图：每条无向边只建立一个边结点，再通过两个链接域挂入两个端点的边链表，便于边的删除和访问。

十字链表适用范围

十字链表面向有向图：每条弧同时链接到起点的出边链和终点的入边链，可分别高效遍历出边与入边。

图存储中的边数与度数

邻接矩阵中无向图的非零元素数为边数的两倍，有向图的非零元素数就是弧数；邻接表中无向边表结点数为边数的两倍，有向边表结点数就是弧数。矩阵行列及邻接链表分别对应出度、入度和无向图度数。

DAG 的拓扑编号与上三角矩阵

对无环有向图作拓扑排序并按序编号，任意弧 i→j 都满足 i<j，因此邻接矩阵的 1 全在主对角线以上；拓扑序不唯一时任取一种即可。

邻接表转邻接矩阵的复杂度

转换时初始化 n×n 矩阵需 O(n²)，扫描顶点表和边表需 O(n+e)，严格总复杂度为 O(n²+e)。若题设已保证矩阵预先清零，只计填边扫描则为 O(n+e)。

最小生成树的存在性与唯一性

无向连通图必有至少一棵最小生成树；边权互异时 MST 唯一，但存在等权竞争边时可能有多棵。MST 不唯一不影响最小总代价的唯一性。

Prim 与 Kruskal 的结果关系

Prim 按顶点集合扩展，Kruskal 按边权递增并避开环路。MST 唯一时二者得到同一棵树；MST 不唯一时可能得到不同树，但总代价相同。

MST 不唯一与原图边数

含 n 个顶点的连通图若只有 n−1 条边，则原图本身就是唯一生成树；因此 MST 不唯一时原图边数必大于 n−1。不同 MST 的总代价始终相同。

Prim 的割边候选

Prim 每一步只能从割 (U,V−U) 的横切边中选取候选，即一端在已选顶点集合 U、另一端在未选集合 V−U；U 内部边和已选边不属于候选。

边权互异保证 MST 唯一

在无向连通图中，所有边权互异会使 Kruskal/Prim 每一步的最小合法边唯一，从而保证最小生成树唯一；反之有等权边并不必然导致多棵 MST。

Kruskal 先判环再选边

Kruskal 按权值递增尝试加入边，但若边的两个端点已经属于同一连通分量，加入会形成回路，必须跳过；因此“当前权值最小”不等于“必然选入”。

Dijkstra 与 Floyd 的适用边界

Dijkstra 求单源最短路，要求边权非负；对每个源点重复运行的朴素复杂度为 O(n³)。Floyd 求全体点对最短路可含负边，但不能有负权回路。

Dijkstra 已确定集合不可回改

Dijkstra 将顶点加入 S 后，其源点最短距离已确定；后续松弛只更新 V−S 中顶点的暂定距离，不会改变已确定路径。

最短路径可取简单路径

若一条候选路径重复顶点，则含有回路；在无负权回路的通常最短路问题中，删除回路不会增加长度，因此存在一条不重复顶点的简单最短路径。