数据结构：图

---

📈 一，图的定义与基本术语

图（Graph）是一种比树更复杂的非线性数据结构，它通过顶点和边的关系表达多对多的关联关系，广泛应用于社交网络、路径规划、电路设计等领域。

（一）图的定义

图由顶点集和边集组成，记为 G = (V, E)，其中：

• 顶点集（V）：由具有相同特性的数据元素组成的非空有限集合，每个元素称为顶点（Vertex）；
• 边集（E）：由顶点之间的关系组成的有限集合，每条关系称为边（Edge）。

根据边是否有方向，图可分为两类：

• 无向图：边是无序对，记为 (v, w)，表示顶点v和w之间存在双向关系（如朋友关系）；
• 有向图：边是有序对，记为 <v, w>，表示从顶点v到w的单向关系（如网页链接、航班路线）。

（二）图的基本术语

• 端点与邻接点：若边 (v, w) 或 <v, w> 存在，则v和w互为端点，也称邻接点；
• 完全图：
  • 无向完全图：任意两顶点间都有边，n个顶点的无向完全图有 n(n-1)/2 条边；
  • 有向完全图：任意两顶点间都有双向边，n个顶点的有向完全图有 n(n-1) 条边；
• 稀疏图与稠密图：边数远少于完全图的图为稀疏图，反之为稠密图（通常以 n log n 为界）；
• 顶点的度：
  • 无向图中，顶点v的度是与v相关联的边数，记为 TD(v)；
  • 有向图中，顶点v的入度是指向v的边数（ID(v)），出度是从v出发的边数（OD(v)），总度 TD(v) = ID(v) + OD(v)；
• 路径与路径长度：路径是顶点序列 v₀→v₁→…→vₖ，路径长度为边的数量；
• 连通与连通分量：
  • 无向图中，若两顶点间存在路径，则为连通；图中最大连通子图称为连通分量；
  • 有向图中，若任意两顶点间双向可达，则为强连通；最大强连通子图称为强连通分量；
• 子图：若图 G' = (V', E') 满足 V'⊆V 且 E'⊆E，则G’是G的子图；
• 网：边带权值的图（如表示距离、成本的图）。

🌰 二，案例引入

场景1：社交网络关系图

在微信好友关系中：

• 每个用户是一个顶点；
• 好友关系是无向边（A是B的好友等价于B是A的好友）；
• 问题：如何找到两人之间的最短好友链（“六度分隔理论”验证）？如何发现紧密联系的朋友圈（连通分量）？

场景2：城市交通路网

在高德地图的路径规划中：

• 城市是顶点，道路是边；
• 有向边表示单行道，边的权值表示距离或通行时间；
• 核心需求：寻找两城市间的最短路径（Dijkstra算法）、判断路网是否连通（避免孤立城市）。

这些案例表明，图结构擅长表达复杂的多对多关系，而图的存储和遍历算法是解决此类问题的基础。

📋 三，图的类型定义

图的抽象数据类型（ADT）定义如下，涵盖图的基本操作：

ADT Graph {数据：顶点集V和边集E，顶点具有唯一标识，边表示顶点间的关系（可带权）。操作：1. CreateGraph(&G, V, E)：根据顶点集V和边集E创建图G。2. DestroyGraph(&G)：销毁图G，释放内存。3. LocateVex(G, u)：返回顶点u在图G中的位置。4. GetVex(G, v)：返回顶点v的值。5. PutVex(&G, v, value)：修改顶点v的值为value。6. FirstAdjVex(G, v)：返回顶点v的第一个邻接点。7. NextAdjVex(G, v, w)：返回顶点v在w之后的下一个邻接点。8. InsertVex(&G, v)：向图G中插入新顶点v。9. DeleteVex(&G, v)：从图G中删除顶点v及相关边。10. InsertArc(&G, v, w)：向图G中插入边<v, w>或(v, w)。11. DeleteArc(&G, v, w)：从图G中删除边<v, w>或(v, w)。12. DFSTraverse(G, visit())：深度优先遍历图G，对每个顶点调用visit()。13. BFSTraverse(G, visit())：广度优先遍历图G，对每个顶点调用visit()。
}

💾 四，图的存储结构

图的存储需高效表达顶点及边的关系，常用结构包括邻接矩阵、邻接表、十字链表和邻接多重表，选择需结合图的类型（有向/无向）和操作需求。

（一）邻接矩阵

核心思想：用二维数组（矩阵）存储顶点间的邻接关系，行和列分别对应顶点。

1. 无向图的邻接矩阵

• 定义：若存在边 (vᵢ, vⱼ)，则 adj[i][j] = adj[j][i] = 1（无权图）或权值（网）；否则为0或∞。
• 示例：3个顶点的无向图 G = ({v0,v1,v2}, {(v0,v1), (v0,v2)}) 的邻接矩阵为：

  [[0, 1, 1],[1, 0, 0],[1, 0, 0]
  ]
  

2. 有向图的邻接矩阵

• 定义：若存在边 <vᵢ, vⱼ>，则 adj[i][j] = 1 或权值；否则为0或∞（矩阵不一定对称）。
• 示例：3个顶点的有向图 G = ({v0,v1,v2}, {<v0,v1>, <v1,v2>}) 的邻接矩阵为：

  [[0, 1, 0],[0, 0, 1],[0, 0, 0]
  ]
  

3. 存储表示（C语言）

#define MAX_VERTEX_NUM 20  // 最大顶点数
typedef char VertexType;   // 顶点数据类型
typedef int EdgeType;      // 边权值类型（0/1表示无权图）typedef struct {VertexType vexs[MAX_VERTEX_NUM];  // 顶点数组EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵int vexnum, arcnum;  // 顶点数和边数int kind;  // 图的类型（无向图/有向图/网）
} MGraph;

4. 优缺点

• 优势：
  • 直观易理解，适合稠密图；
  • 判断两顶点是否相邻、求顶点度（无向图看行/列和，有向图看行和为出度、列和为入度）效率高（O(1)）。
• 劣势：
  • 空间复杂度高（O(n²)），不适合稀疏图；
  • 插入/删除顶点需重构矩阵，操作繁琐。

（二）邻接表

核心思想：数组存储顶点，每个顶点通过链表存储其邻接点，结合顺序存储和链式存储的优势。

1. 无向图的邻接表

• 结构：顶点数组 + 邻接链表，每个链表节点存储邻接顶点的下标和指针。
• 示例：无向图 G = ({v0,v1,v2}, {(v0,v1), (v0,v2)}) 的邻接表：

  v0 → 1 → 2 → NULL  
  v1 → 0 → NULL  
  v2 → 0 → NULL  
  

  （每个边在链表中出现两次，如 (v0,v1) 同时出现在v0和v1的链表中）。

2. 有向图的邻接表

• 结构：与无向图类似，但链表仅存储出边对应的邻接点（出边表）；若需入边信息，可增设逆邻接表（存储入边对应的邻接点）。
• 示例：有向图 G = ({v0,v1,v2}, {<v0,v1>, <v1,v2>}) 的邻接表：

  v0 → 1 → NULL  
  v1 → 2 → NULL  
  v2 → NULL  
  

3. 存储表示（C语言）

// 邻接表节点
typedef struct ArcNode {int adjvex;  // 邻接顶点下标struct ArcNode *nextarc;  // 下一个邻接点EdgeType weight;  // 边的权值（网用）
} ArcNode;// 顶点节点
typedef struct VNode {VertexType data;  // 顶点数据ArcNode *firstarc;  // 指向第一个邻接点
} VNode, AdjList[MAX_VERTEX_NUM];// 图结构
typedef struct {AdjList vertices;  // 邻接表数组int vexnum, arcnum;  // 顶点数和边数int kind;  // 图的类型
} ALGraph;

4. 优缺点

• 优势：
  • 空间复杂度低（O(n + e)，n为顶点数，e为边数），适合稀疏图；
  • 遍历邻接点、插入边操作高效（O(1)定位顶点，链表插入O(1)）。
• 劣势：
  • 无向图中边信息存储重复（占用双倍空间）；
  • 判断两顶点是否相邻需遍历链表（O(n)），效率低于邻接矩阵。

（三）十字链表

核心思想：专为有向图设计，同时存储出边和入边信息，每个边节点同时属于一个出边链表和一个入边链表。

1. 结构组成

• 顶点节点：存储顶点数据、出边表头指针（firstout）、入边表头指针（firstin）；
• 边节点：存储起点下标（tailvex）、终点下标（headvex）、下一条出边指针（hlink）、下一条入边指针（tlink）、权值（网用）。

2. 示例

有向图 G = ({v0,v1,v2}, {<v0,v1>, <v1,v2>, <v0,v2>}) 的十字链表：

• 顶点v0的出边链表：<v0,v1> → <v0,v2>；
• 顶点v1的出边链表：<v1,v2>；
• 顶点v2的入边链表：<v0,v2> → <v1,v2>。

3. 存储表示（C语言）

// 十字链表边节点
typedef struct ArcBox {int tailvex, headvex;  // 起点、终点下标struct ArcBox *hlink, *tlink;  // 入边链表指针、出边链表指针EdgeType weight;  // 权值
} ArcBox;// 十字链表顶点节点
typedef struct VexNode {VertexType data;ArcBox *firstin, *firstout;  // 入边表头、出边表头
} VexNode;// 有向图十字链表结构
typedef struct {VexNode xlist[MAX_VERTEX_NUM];  // 顶点数组int vexnum, arcnum;  // 顶点数和边数
} OLGraph;

4. 优势

• 同时支持出边和入边的高效遍历，适合需频繁访问入度/出度的场景（如拓扑排序）；
• 空间复杂度与邻接表相当（O(n + e)），无数据冗余。

（四）邻接多重表

核心思想：专为无向图设计，解决邻接表中边信息重复存储的问题，每条边仅用一个节点表示，同时关联两个顶点的链表。

1. 结构组成

• 顶点节点：存储顶点数据、第一条边指针（firstedge）；
• 边节点：存储两个顶点下标（ivex, jvex）、分别指向两顶点的下一条边（ilink, jlink）、标志位（mark，用于标记是否访问）。

2. 示例

无向图 G = ({v0,v1,v2}, {(v0,v1), (v0,v2), (v1,v2)}) 的邻接多重表：

• 边 (v0,v1) 同时出现在v0的边链表和v1的边链表中；
• 通过ilink和jlink指针串联同一顶点的所有边，无需重复存储。

3. 存储表示（C语言）

// 邻接多重表边节点
typedef struct EBox {int mark;  // 访问标记int ivex, jvex;  // 两顶点下标struct EBox *ilink, *jlink;  // 分别指向两顶点的下一条边EdgeType weight;  // 权值（网用）
} EBox;// 邻接多重表顶点节点
typedef struct VexBox {VertexType data;EBox *firstedge;  // 指向第一条边
} VexBox;// 无向图邻接多重表结构
typedef struct {VexBox adjmulist[MAX_VERTEX_NUM];  // 顶点数组int vexnum, arcnum;  // 顶点数和边数
} AMLGraph;

4. 优势

• 每条边仅存储一次，节省空间；
• 便于边的遍历和删除操作（如无向图的边删除只需操作一个节点），适合需频繁修改边的场景（如地图路径更新）。

🔍 五，图的遍历

图的遍历是按某种规则访问图中所有顶点且仅访问一次的过程，是图论算法的基础。常用的遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。

（一）深度优先搜索

深度优先搜索（Depth-First Search, DFS）模拟“回溯探索”过程，优先沿着一条路径深入，无法前进时退回上一节点选择新路径。

核心思想

1. 从起点顶点v出发，标记v为“已访问”；
2. 任选v的一个未访问邻接点w，递归执行DFS(w)；
3. 若v的所有邻接点均已访问，则回溯至v的前驱节点，重复步骤2；
4. 若图非连通，需对未访问的孤立顶点重复上述过程。

示例（无向图）

对图 G = ({v0,v1,v2,v3}, {(v0,v1), (v0,v2), (v1,v3)}) 执行DFS：

• 起点v0→访问v0→邻接点v1未访问→访问v1→邻接点v3未访问→访问v3→v3无未访问邻接点→回溯至v1→v1无新邻接点→回溯至v0→邻接点v2未访问→访问v2→遍历结束。
• 遍历序列：v0→v1→v3→v2。

代码实现（邻接表存储）

bool visited[MAX_VERTEX_NUM];  // 访问标记数组// 从顶点v出发深度优先遍历
void DFS(ALGraph G, int v) {visited[v] = true;  // 标记当前顶点为已访问printf("%c ", G.vertices[v].data);  // 访问顶点ArcNode *p = G.vertices[v].firstarc;  // 指向第一个邻接点while (p != NULL) {int w = p->adjvex;  // 邻接点下标if (!visited[w]) {  // 若未访问，递归遍历DFS(G, w);}p = p->nextarc;  // 访问下一个邻接点}
}// 深度优先遍历整个图（处理非连通图）
void DFSTraverse(ALGraph G) {for (int v = 0; v < G.vexnum; v++) {visited[v] = false;  // 初始化访问标记}for (int v = 0; v < G.vexnum; v++) {if (!visited[v]) {  // 对未访问的顶点启动DFSDFS(G, v);}}
}

特点

• 递归实现依赖栈（系统栈或手动栈），空间复杂度为O(n)（最坏情况为链状图）；
• 时间复杂度：邻接表存储为O(n + e)，邻接矩阵存储为O(n²)；
• 遍历序列不唯一，取决于邻接点的访问顺序。

（二）广度优先搜索

广度优先搜索（Breadth-First Search, BFS）模拟“层次扩展”过程，优先访问当前顶点的所有邻接点，再按同样规则访问下一层次顶点。

核心思想

1. 从起点顶点v出发，标记v为“已访问”并将其入队；
2. 队列非空时，出队顶点u，访问u的所有未访问邻接点，标记后入队；
3. 重复步骤2，直至队空；
4. 若图非连通，对未访问的孤立顶点重复上述过程。

示例（无向图）

对上述无向图执行BFS：

• 起点v0入队→v0出队→访问v0→邻接点v1、v2入队→v1出队→访问v1→邻接点v3入队→v2出队→访问v2→v3出队→访问v3→队空→遍历结束。
• 遍历序列：v0→v1→v2→v3。

代码实现（邻接表存储）

// 广度优先遍历
void BFS(ALGraph G, int v) {int queue[MAX_VERTEX_NUM], front = 0, rear = 0;  // 队列printf("%c ", G.vertices[v].data);  // 访问起点visited[v] = true;queue[rear++] = v;  // 起点入队while (front != rear) {  // 队列非空int u = queue[front++];  // 出队ArcNode *p = G.vertices[u].firstarc;while (p != NULL) {int w = p->adjvex;if (!visited[w]) {  // 未访问的邻接点printf("%c ", G.vertices[w].data);visited[w] = true;queue[rear++] = w;  // 入队}p = p->nextarc;}}
}// 广度优先遍历整个图
void BFSTraverse(ALGraph G) {for (int v = 0; v < G.vexnum; v++) {visited[v] = false;}for (int v = 0; v < G.vexnum; v++) {if (!visited[v]) {BFS(G, v);}}
}

特点

• 依赖队列实现，空间复杂度为O(n)（最坏情况队列存储所有顶点）；
• 时间复杂度与DFS相同：邻接表O(n + e)，邻接矩阵O(n²)；
• 遍历序列唯一（按层次访问），适合寻找最短路径（无权图中层次即最短路径长度）。

💡 六，图的应用

（一）最小生成树

生成树：连通图的极小连通子图，包含所有顶点和n-1条边（无回路）。最小生成树（MST） 是边权值之和最小的生成树，应用于通信网络布线、管道铺设等成本优化场景。

1. Prim算法（加点法）

思想：从任意顶点出发，逐步添加连接树内外顶点的最小权值边，直至包含所有顶点。

• 时间复杂度：O(n²)，适合稠密图。

2. Kruskal算法（加边法）

思想：将所有边按权值升序排序，依次添加不形成回路的边，直至添加n-1条边。

• 需用并查集判断回路，时间复杂度：O(e log e)，适合稀疏图。

（二）最短路径

最短路径：两顶点间权值之和最小的路径，应用于导航路线规划、网络路由优化等。

1. Dijkstra算法

功能：求单源最短路径（从起点到其他所有顶点的最短路径）。
思想：维护“已确定最短路径的顶点集”，每次选择距离起点最近的未确定顶点，更新其邻接点的距离。

• 时间复杂度：O(n²)（邻接矩阵）或O(e log n)（邻接表+优先队列）；
• 局限：不支持负权边。

2. Floyd算法

功能：求任意两顶点间的最短路径。
思想：通过动态规划，依次以每个顶点为中间点，更新所有顶点对的距离。

• 时间复杂度：O(n³)，适合顶点数较少的图；
• 支持负权边，但不支持负权回路。

（三）拓扑排序

拓扑排序：对有向无环图（DAG）的顶点进行线性排序，使所有有向边从排序靠前的顶点指向靠后的顶点，应用于任务调度、课程安排等依赖关系场景。

算法步骤

1. 计算所有顶点的入度，入度为0的顶点入队；
2. 队非空时，出队顶点v并加入排序序列，删除v的所有出边，更新邻接点入度；
3. 若邻接点入度变为0，入队；
4. 重复步骤2-3，若排序序列长度小于顶点数，则图存在环（无法拓扑排序）。

示例

课程依赖图 C1→C2→C3，拓扑排序结果可为 C1→C2→C3 或 C1→C3→C2（若C1也直接指向C3）。

（四）关键路径

关键路径：有向无环图中从起点到终点的最长路径，决定整个工程的最短完成时间，应用于项目管理、进度规划。

核心概念

• 事件最早发生时间：从起点到该事件的最长路径长度；
• 事件最迟发生时间：不延误总工期的最晚发生时间；
• 活动最早开始时间：等于其起点事件的最早发生时间；
• 活动最迟开始时间：等于其终点事件的最迟发生时间减去活动持续时间；
• 关键活动：最早开始时间等于最迟开始时间的活动，其延误将导致总工期延长。

算法步骤

1. 拓扑排序确定事件顺序；
2. 从前向后计算事件最早发生时间和活动最早开始时间；
3. 从后向前计算事件最迟发生时间和活动最迟开始时间；
4. 找出关键活动，组成关键路径。

🛠️ 七，案例分析与实现

案例：校园导航系统（最短路径查询）

功能：输入校园内两个地点（顶点），输出两点间的最短路径及距离（权值为地点间的步行距离）。

实现思路

1. 用邻接矩阵存储校园地图（顶点为地点，边权为距离）；
2. 基于Dijkstra算法实现单源最短路径查询；
3. 输出路径时通过前驱数组回溯路径。

核心代码

#define INF 32767  // 表示无穷大（不可达）// Dijkstra算法求单源最短路径
void Dijkstra(MGraph G, int v0, int dist[], int path[]) {int n = G.vexnum;bool final[n];  // 标记是否确定最短路径for (int v = 0; v < n; v++) {dist[v] = G.arcs[v0][v];  // 初始化距离为v0到v的直接距离final[v] = false;if (dist[v] < INF) path[v] = v0;  // 前驱为v0else path[v] = -1;  // 无前驱}dist[v0] = 0;  // 起点到自身距离为0final[v0] = true;// 确定其余n-1个顶点的最短路径for (int i = 1; i < n; i++) {// 选择距离v0最近的未确定顶点uint min = INF, u = v0;for (int v = 0; v < n; v++) {if (!final[v] && dist[v] < min) {min = dist[v];u = v;}}final[u] = true;  // 标记u为已确定// 更新u的邻接点距离for (int v = 0; v < n; v++) {if (!final[v] && G.arcs[u][v] < INF && dist[u] + G.arcs[u][v] < dist[v]) {dist[v] = dist[u] + G.arcs[u][v];  // 更新距离path[v] = u;  // 更新前驱}}}
}// 输出从v0到v的最短路径
void PrintPath(MGraph G, int path[], int v0, int v) {if (v == v0) {printf("%c", G.vexs[v]);return;}PrintPath(G, path, v0, path[v]);  // 递归打印前驱printf("→%c", G.vexs[v]);
}int main() {MGraph G;// 初始化校园地图（示例：5个地点，邻接矩阵存储距离）G.vexnum = 5;G.vexs[0] = '图书馆'; G.vexs[1] = '教学楼'; G.vexs[2] = '食堂';G.vexs[3] = '操场'; G.vexs[4] = '宿舍';// 初始化邻接矩阵（INF表示不可达）int arcs[5][5] = {{0, 10, INF, 30, 100},{10, 0, 50, INF, INF},{INF, 50, 0, 20, 10},{30, INF, 20, 0, 60},{100, INF, 10, 60, 0}};for (int i = 0; i < 5; i++) {for (int j = 0; j < 5; j++) {G.arcs[i][j] = arcs[i][j];}}int v0 = 0, v = 4;  // 查询从图书馆（0）到宿舍（4）的最短路径int dist[5], path[5];Dijkstra(G, v0, dist, path);printf("最短路径：");PrintPath(G, path, v0, v);printf("\n最短距离：%d米\n", dist[v]);// 输出：最短路径：图书馆→操场→食堂→宿舍，最短距离：60米return 0;
}

📝 章结

图作为表达多对多关系的核心数据结构，其理论和算法渗透在计算机科学的各个领域：

• 图的本质：突破了线性表和树的结构限制，通过顶点和边的灵活组合，建模现实世界中复杂的关联关系（如社交网络、交通路网）。理解图的基本术语（度、路径、连通性）是掌握后续算法的基础。

• 存储与遍历：邻接矩阵和邻接表是两种基础存储结构，分别适合稠密图和稀疏图；深度优先搜索（DFS）和广度优先搜索（BFS）是图遍历的两种核心方法，DFS依赖栈实现回溯探索，BFS依赖队列实现层次扩展，二者为后续应用算法提供了基础框架。

• 经典应用算法：

  • 最小生成树（Prim/Kruskal）解决了“连接所有节点的最低成本”问题；
  • 最短路径算法（Dijkstra/Floyd）实现了不同场景下的路径优化；
  • 拓扑排序和关键路径则为依赖关系调度和项目进度规划提供了量化工具。

图的学习核心在于“问题建模”和“算法选择”：面对实际问题时，需先将其抽象为图结构（顶点、边、权值的定义），再根据图的类型（有向/无向、稀疏/稠密）和问题需求（路径、连通性、调度）选择合适的算法。从数据结构到算法实现，图的知识体系充分体现了“结构决定操作，操作服务需求”的计算机科学思想。