数据结构与算法-知识点(第六章图结构)

张沉 4/11/2025 13003

# 1. 图的基本概念与基本操作

# 识记知识点

图（Graph）
- 定义：由顶点（Vertex）和边（Edge）组成的集合，表示为 ( G = (V, E) )，其中 ( V ) 是顶点集，( E ) 是边集。
- 顶点（Vertex/Node）：图的基本元素，表示实体或对象。
- 边（Edge/Arc）：连接两个顶点的关系，分为无向边和有向边。
  - 无向边（Undirected Edge）：无方向性，如 ((v_i, v_j))。
  - 有向边（Directed Edge/弧）：有方向性，如 (\langle v_i, v_j \rangle)，其中 (v_i) 是弧尾（起点），(v_j) 是弧头（终点）。
子图（Subgraph）
- 若图 (G' = (V', E')) 满足 (V' \subseteq V) 且 (E' \subseteq E)，则 (G') 是 (G) 的子图。
稀疏图（Sparse Graph）与密集图（Dense Graph）
- 稀疏图：边数远少于最大可能边数的图。
- 密集图：边数接近最大可能边数的图。
- 最大边数：
  - 无向图：( \frac{n(n-1)}{2} )（(n)为顶点数）。
  - 有向图：( n(n-1) )。
带权图（Weighted Graph）
- 边或弧附带数值（权），如距离、成本等，称为带权图或网（Network）。
邻接点（Adjacent Vertices）
- 若边 ((v_i, v_j)) 存在，则 (v_i) 和 (v_j) 互为邻接点。
- 对于有向边 (\langle v_i, v_j \rangle)，(v_i) 是 (v_j) 的直接前驱，(v_j) 是 (v_i) 的直接后继。
度（Degree）、入度（In-degree）、出度（Out-degree）
- 度（TD(v)）：顶点 (v) 的边数。
- 入度（ID(v)）：以 (v) 为终点的有向边数。
- 出度（OD(v)）：以 (v) 为起点的有向边数。
- 对于有向图：( \text{TD}(v) = \text{ID}(v) + \text{OD}(v) )。
完全图（Complete Graph）
- 无向图中任意两顶点间均有边；有向图中任意两顶点间均有方向相反的两条弧。
路径（Path）
- 顶点序列 (v_0, e_1, v_1, e_2, ..., v_k)，其中每条边 (e_i) 连接 (v_{i-1}) 和 (v_i)。
- 路径长度：边数或边权之和。
- 简单路径：顶点不重复的路径。
- 回路（Cycle）/环：路径首尾顶点相同且长度≥1，且除首尾外无重复顶点的路径称为简单回路。
连通图（Connected Graph）
- 无向图中任意两顶点间有路径。
- 连通分量（Connected Component）：极大连通子图。
- 强连通图（Strongly Connected Graph）：有向图中任意两顶点间存在双向路径。
- 弱连通图：将有向边视为无向边后构成连通图。

# 领会知识点

顶点与边的关联性
- 边 ((v_i, v_j)) 关联顶点 (v_i) 和 (v_j)。
- 对于有向边 (\langle v_i, v_j \rangle)，关联方向性：(v_i \rightarrow v_j)。
邻接的含义
- 无向图中，边 ((v_i, v_j)) 的两个顶点互为邻接点。
- 有向图中，邻接仅单向：若 (\langle v_i, v_j \rangle) 存在，则 (v_i) 邻接到 (v_j)。
度与边的关系
- 无向图：所有顶点度数之和等于边数的两倍。
- 有向图：所有顶点入度之和等于出度之和，且等于边数。

# 简单应用

判断图的类型
- 给定图 (G)，若所有边无方向，则为无向图；若边有方向且无环，则为有向无环图（DAG）。
计算顶点度数
- 例如，有向图中顶点 (v) 的出度为3，入度为2，则总度数为5。

# 2. 图的存储结构及基本操作

# 识记知识点

邻接矩阵（Adjacency Matrix）
- 用二维数组 (A) 存储：
  - (A[i][j] = 1) 表示顶点 (v_i) 和 (v_j) 间有边（无向图）或弧（有向图）。
  - 可附加权值存储边的权重。
- 优点：快速判断边的存在性；适合稠密图。
- 缺点：空间复杂度 (O(n^2))，稀疏图浪费空间。
邻接表（Adjacency List）
- 用链表或数组模拟的动态结构：
  - 每个顶点对应一个链表，存储其邻接顶点。
  - 无向图：每条边在两个顶点的链表中出现一次。
  - 有向图：弧头顶点出现在弧尾的链表中。
- 逆邻接表：仅用于有向图，记录顶点的入边。
表结点（Edge Node）
- 邻接表中每个节点存储邻接顶点和边的权值。

# 领会知识点

邻接矩阵与邻接表的对比

| 特性 | 邻接矩阵 | 邻接表 | |---------------------|----------------------------------|--------------------------------| | 空间复杂度 | (O(n^2)) | (O(n + e)) | | 判断边存在性 | (O(1)) | (O(k))（k为顶点度数） | | 适合场景 | 稠密图 | 稀疏图 |
逆邻接表的作用
- 用于有向图，快速获取顶点的入边信息，常用于计算入度。

# 简单应用

构建邻接矩阵 无向图 (G = (V={A,B,C}, E={(A,B),(B,C)})) 的邻接矩阵： [ \begin{matrix} & A & B & C \ A & 0 & 1 & 0 \ B & 1 & 0 & 1 \ C & 0 & 1 & 0 \ \end{matrix} ]
邻接表实现 有向图的邻接表：
```
A → B  
B → C  
C → (无)
```

# 3. 图的搜索

# 识记知识点

深度优先搜索（DFS, Depth-First Search）
- 类似树的前序遍历，采用栈或递归实现。
- 步骤：
  1. 访问起始顶点。
  2. 递归访问当前顶点的未访问邻接顶点。
- 应用：路径搜索、连通性判断。
广度优先搜索（BFS, Breadth-First Search）
- 类似树的层序遍历，采用队列实现。
- 步骤：
  1. 访问起始顶点。
  2. 依次访问当前顶点的未访问邻接顶点，并入队。
- 应用：最短路径（无权图）、层次遍历。

# 领会知识点

搜索序列的差异
- DFS：优先深入探索分支，序列可能为 (A \rightarrow B \rightarrow D \rightarrow C)。
- BFS：逐层扩展，序列可能为 (A \rightarrow B \rightarrow C \rightarrow D)。
辅助数据结构
- DFS：栈（或递归调用栈）。
- BFS：队列。

# 简单应用

DFS实现示例（邻接表）

def dfs(graph, start, visited):
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

BFS实现示例（邻接表）

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 4. 图的生成树

# 识记知识点

生成树（Spanning Tree）
- 连通图的极小连通子图，包含所有顶点且无环，边数为 (n-1)。
- 生成森林：非连通图的每个连通分量的生成树构成森林。
深度优先生成树（DFS Tree）
- 通过DFS遍历生成的树，边分为树边和回边。
广度优先生成树（BFS Tree）
- 通过BFS遍历生成的树，边分为树边和叉边。
最小生成树（MST, Minimum Spanning Tree）
- 带权图中边权之和最小的生成树。
- 应用场景：网络设计、电路布线。

# 领会知识点

最小生成树的性质
- 连通性：必须连通。
- 无环性：树结构。
- 边权最小性：总权值最小。
普里姆算法（Prim）
- 思想：从一个顶点出发，逐步加入离当前树最近的顶点。
- 时间复杂度：(O(n^2))（邻接矩阵）或 (O(e \log n))（堆优化）。
克鲁斯卡尔算法（Kruskal）
- 思想：按边权从小到大选择，避免形成环。
- 时间复杂度：(O(e \log e))（排序）。

# 简单应用

Prim算法步骤
1. 从任意顶点（如 (A)）开始，加入集合 (S)。
2. 找到连接 (S) 和 (V-S) 的最小边（如 (A-B)），加入生成树。
3. 重复直到所有顶点在 (S) 中。
Kruskal算法步骤
1. 将所有边按权排序。
2. 依次选择最小边，若不形成环则加入生成树。
3. 直到生成树有 (n-1) 条边。

# 5. 有向无环图（DAG）及其应用

# 识记知识点

AOV网（Activity On Vertex Network）
- 顶点表示活动，边表示活动间的优先关系。
- 源点：无前驱的顶点。
- 汇点：无后继的顶点。
拓扑排序（Topological Sort）
- 对AOV网进行拓扑排序，得到一个线性序列，满足所有前驱在后驱之前。
- 拓扑序列：如 (A \rightarrow B \rightarrow C)，表示先做 (A)，再做 (B)，最后做 (C)。
关键路径（Critical Path）
- 在AOE网（边表示活动，顶点表示事件）中，路径长度最长的路径。
- 关键活动：在关键路径上的活动。

# 领会知识点

拓扑排序的步骤
1. 计算所有顶点的入度。
2. 选择入度为0的顶点加入序列。
3. 移除该顶点及其边，更新入度。
4. 重复直到无顶点或存在环。
关键路径的计算
- 最早开始时间（ve）：顶点事件的最早发生时间。
- 最迟开始时间（vl）：顶点事件的最晚发生时间，且不延误整个工程。
- 时间余量（sl）：(sl(v) = vl(v) - ve(v))，若为0则为关键活动。

# 简单应用

判断有向图是否存在环
- 若拓扑排序后顶点数小于图的顶点数，则存在环。
拓扑排序示例 图 (G) 的邻接表：
```
A → B  
B → C  
C → D
```
拓扑序列：(A \rightarrow B \rightarrow C \rightarrow D)。

# 6. 最短路径

# 识记知识点

单源最短路径（SSSP）
- 从某一顶点（源点）出发到其他所有顶点的最短路径。
所有点对的最短路径（APSP）
- 求每对顶点之间的最短路径。

# 领会知识点

Dijkstra算法
- 适用：无负权边的带权图。
- 思想：贪心策略，每次选择离源点最近的顶点。
- 时间复杂度：(O(n^2))（邻接矩阵）或 (O(e + n \log n))（堆优化）。
Floyd算法
- 适用：可处理负权边（但无负权环）。
- 思想：动态规划，逐步考虑所有顶点作为中间节点。
- 时间复杂度：(O(n^3))。

记沉

Choose mode

数据结构与算法-知识点(第六章图结构)

数据结构与算法-知识点(第六章图结构)

# 1. 图的基本概念与基本操作

# 识记知识点

# 领会知识点

# 简单应用

# 2. 图的存储结构及基本操作

# 识记知识点

# 领会知识点

# 简单应用

# 3. 图的搜索

# 识记知识点

# 领会知识点

# 简单应用

# 4. 图的生成树

# 识记知识点

# 领会知识点

# 简单应用

# 5. 有向无环图（DAG）及其应用

# 识记知识点

# 领会知识点

# 简单应用

# 6. 最短路径

# 识记知识点

# 领会知识点