图的基本分类#

完全图#

边数达到上限的简单图称为完全图：

• 子图：G’ = (V’, E’)，满足 V’ ⊆ V 且 E’ ⊆ E（注意 E’ 中的边关联的顶点必须在 V’ 中）
• 生成子图：V’ = V 的子图，即包含全部顶点的子图

易错：V 的任意子集和 E 的任意子集不一定能构成子图——E’ 中的边所关联的顶点必须在 V’ 中。

握手定理（高频考点）#

其中 e 为边（弧）的数量。该公式是选择题中求边数或度数的核心工具。

无向图的连通性#

• 连通：顶点 v 到 w 之间存在路径
• 连通图：任意两个顶点都连通
• 连通分量：无向图中的极大连通子图

有向图的连通性#

• 强连通：顶点 v 到 w 和 w 到 v 之间都存在路径
• 强连通图：任意两个顶点都强连通
• 强连通图至少需要 n 条弧（构成一个环）
• 强连通分量：有向图中的极大强连通子图

易错：“连通”（无向图）与”强连通”（有向图）不同。n 个顶点的强连通图至少需要 n 条边（构成一个环）。

连通分量与强连通分量#

连通分量（无向图）：无向图中的极大连通子图。连通图只有一个连通分量（即其自身），非连通图有多个。“极大”的含义：不能再加入更多的顶点和边使其仍然连通。

强连通分量（有向图）：有向图中的极大强连通子图。任何一个顶点本身构成一个强连通分量。求强连通分量的方法：对图进行两次 DFS（Kosaraju 算法 / Tarjan 算法）。

邻接矩阵#

存储方式：用二维数组 A[i][j] 表示顶点 i 与 j 的关系。无向图的邻接矩阵是对称矩阵。

无权图：A[i][j] = 1 表示存在边，0 表示不存在。 带权图：A[i][j] = w 表示边权，∞ 表示不存在边。

1
#define MaxVertexNum 100
2
typedef struct {
3
    char vex[MaxVertexNum];
4
    int edge[MaxVertexNum][MaxVertexNum];
5
    int vexNum, edgeNum;
6
} MGraph;

度的计算：

• 无向图：顶点 i 的度 = 第 i 行（或列）非零元素个数
• 有向图出度 OD(i) = 第 i 行非零元素个数
• 有向图入度 ID(i) = 第 i 列非零元素个数

重要性质：A^n[i][j] 表示顶点 i 到 j 长度为 n 的路径条数。

邻接表#

存储方式：长度为 V 的顶点数组 + 每条顶点对应一条边链表。

1
typedef struct ArcNode {
2
    int adjvex;
3
    struct ArcNode *next;
4
} ArcNode;
5

6
typedef struct VNode {
7
    char data;
8
    ArcNode *first;
9
} VNode, AdjList[MaxVertexNum];
10

11
typedef struct {
12
    AdjList vertices;
13
    int vexnum, arcnum;
14
} ALGraph;

特点：

• 无向图边结点数为 2E，有向图边结点数为 E
• 邻接表的表示不唯一（链表结点顺序可变）
• 有向图的邻接表只能直接查出出度；如需高效求入度，应使用逆邻接表或十字链表

十字链表（有向图专用）#

弧结点结构：| tailvex | headvex | hlink | tlink | info | 顶点结点结构：| data | firstin | firstout |

• 沿 firstout + tlink 遍历所有出弧（求出度）
• 沿 firstin + hlink 遍历所有入弧（求入度）
• 空间复杂度 O(V+E)，与邻接表相同

邻接多重表（无向图专用）#

边结点结构：| mark | ivex | ilink | jvex | jlink | info | 顶点结点结构：| data | firstedge |

• 每条边只用一个边结点表示，被两个顶点的链表共享
• 删除边只需删除一个结点（邻接表需删两个）
• mark 标志位用于标记边是否已被访问

四种存储结构对比#

易错：十字链表只适用于有向图，邻接多重表只适用于无向图。邻接表中无向边在两个顶点的链表中各存一次（共两个结点），邻接多重表中每条边只存一个结点。