# 图的定义和基本术语

# 图的定义

1. 图：$G=(V,E)$，Graph=(Vertex,Edge)
   1. V：顶点（数据元素）的有穷非空集合
   2. E：边的有穷集合

# 基本术语

1. 无向图：每条边都是无方向的
2. 有向图：每条边都是有方向的
3. 完全图：任意两个节点都有一条边相连
4. 稀疏图：有很少边或弧的图
5. 网：边 / 弧带权的图
6. 邻接：有边 / 弧相连的两个定点之间的关系
   1. 存在$(v_i,v_j)$，则称$v_i$ 和$v_j$ 互为邻接点
   2. 存在$<v_i,v_j>$，则称$v_i$ 邻接到$v_j$，$v_j$ 邻接于$v_i$
7. 关联（依附）：边 / 弧与定点之间的关系，存在$(v_i,v_j)$/$<v_i,v_j>$，则称该边 / 弧关联于$v_i$ 和$v_j$
8. 定点的度：与该定点相关联的数目，记为 TD (v)
   1. 在有向图中，定点的度等于该定点的入度与出度之和
   2. 顶点 v 的出度是以 v 为终点的有向边的条数，记作 ID (v)
   3. 顶点 v 的出度是以 v 为起点的有向边的条数，记作 OD (v)
9. 路径：持续的边构成的顶点序列
10. 路径长度：路径上边或弧的数目 / 权值之和
11. 回路（环）：第一个顶点和最后一个顶点相同的路径
12. 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径
13. 简单回路（简单环）：除路径起点和重点相同外，其余顶点均不相同的路径
14. 连通图：
    1. 强连通图：在无（有）向图中$G=(V,{E})$ 中，若对任何两个顶点 v，u 都存在从 v 到 u 的路径，则称 G 是强连通图
15. 权与网
    1. 权：图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费
    2. 网：带权的图称作网
16. 子图：一个图是另一个图的一部分，则称为子图
17. 生成树：包含无向图 G 所有顶点的极小连通子图
18. 生成森林：对联通图，由各个联通分量的生成树的集合

# 图的类型定义

# 图的抽象数据类型定义

ADT Graph {

​ 数据对象 V：具有相同特性的数据元素的集合，称为顶点集

​ 数据关系 R：R=

​ 基本操作：...

}

# 图的存储结构

# 邻接矩阵

1. 建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）
2. 优点：
   1. 直观、简单、好理解
   2. 方便检查任意一对顶点间是否存在边
   3. 方便找任一顶点的所有邻接点
   4. 方便计算任一顶点的度
3. 缺点：
   1. 不便于增加和删除顶点
   2. 浪费空间 —— 存储稀疏，有大量无效元素
   3. 浪费时间 —— 统计稀疏图中一共有多少条边

# 邻接表

1. 顶点：按编号顺序将顶点数据存放在一维数组中
2. 关联同一顶点的边：用线性链表存储
3. 无向图特点：
   1. 邻接表不唯一
   2. 若无向图有 n 个节点，e 条边，其邻接表需 n 个头节点和 2e 个表节点（多用于存储稀疏图）
4. 有向图特点：
   1. 顶点$v_i$ 的出度为 i 个单链表中的节点个数
   2. 顶点$v_i$ 的入度为整个单链表中邻接点域值是$i-1$ 的节点个数

# 十字链表

# 邻接多重表

# 图的遍历

# 定义

1. 从已给的连通图中某一顶点出发，沿着一些边访问图中所有节点，且使每个节点仅被访问一次，就叫做图的遍历
2. 实质：找每个顶点的邻接点
3. 特点：图中可能有回路，且图的任一顶点都有可能与其它顶点相通
   1. 解决思路：设置辅助数组 visited [n]，用来标记每个被访问过的顶点
4. 遍历方法：
   1. 深度优先搜索 DFS（Depth First Search）
   2. 广度优先搜索 BFS（Breadth First Search）

# 深度优先遍历实现

# 邻接矩阵方式

# DFS 算法效率分析

1. 用邻接矩阵来表示图，遍历图中每个顶点都要从头扫描该顶点，时间复杂度为$O(n^2)$
2. 用邻接表来表示图，虽然有 2e 个表节点，但只需扫描 e 个节点即可完成遍历，加上访问 n 个头节点的时间，时间复杂度为$O(n+e)$

# 广度优先遍历实现

# 图的应用

# 生成树的方法

# 最小生成树

# 定义

最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值最小的那棵生成树称为最小生成树，也叫最小代价生成树

# 普里姆（Prim）算法

1. 算法思想：
   1. 设$N=(V,E)$ 是连通网，TE 是 N 上最小生成树中边的集合
   2. 初始令$U={U_0}$，$u_0\in V$，TE={}
   3. 在所有$u\in U$，$c\in V-U$ 里边$(u,,v)\in E$ 中，找一条代价最小的边$(u_0,v_0)$
   4. 将$(u_0,V_0)$ v 并入集合 TE，同时$v_0$ 并入 U
   5. 重复上述擦欧总直至 U=V 为止，则 T=(V,TE) 为 N 的最小生成树

# 克鲁斯卡尔（Kruskal）算法

1. 算法思想：
   1. 设连通网 N=(V，E)，令最小生成树初状态为只有 n 个顶点而无边的非连通图 T=(V，{})，每个顶点自成一个连通分量
   2. 在 E 中选取代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上（不能形成环），则将此边加入到 T 中，否则，舍去此边，选取下一条代价最小的边
   3. 依次类推，直至 T 中所有顶点都在同一分量上为止

# Prim 与 Kruskal 比较

算法名	算法思想	时间复杂度	适应范围
普里姆	选择点	$O(n^2)$（n 为顶点数）	稠密图
克鲁斯卡尔	选择边	$O(eloge)$（e 为边）	稀疏图

# 最短路径

# 单源最短路径 —— 用 Dijkstra（迪克斯特拉）算法

1. 初始化：先找出从源点$v_0$ 到各终点$v_k$ 得直达路径$(v_0,v-K)$，即通过一条弧到达的路径
2. 选择：从这些路径中找出一条最短的路径
3. 更新：然后对其余各条路径进行适当调整
   1. 若在图中存在弧$(u,v_k)$，且$(v_0,u)+(u,v_k)<(v_0,v_k)$，则以路径$(v_0,u,v_k)$ 代替$(v_0,v_k)$

# 所有顶点间的最短路径 —— 用 Floyd（弗洛伊德）算法

# 拓扑排序

1. 在有向图中选一个没有前驱的顶点且输出之
2. 从图中删除顶点和所有以它为尾的弧
3. 重复上述两部，直至全部顶点均已输出，或者当图中不存在无前驱的顶点为止

# 关键路径