一、图
1. 图的概念
图是一种数据结构，由节点和连接它们的边构成。
数学上，一般使用 \(G = (V, E)\) 表示一个点集为 \(V\)，边集为 \(E\) 的图。
与一个顶点 \(u\) 关联的边的个数叫做顶点 \(u\) 的的度，用 \(d(u)\) 表示。
2. 图的分类
-
按照点或边是否有限：
有限图、无限图。
-
按照边是否有方向：
有向图（所有边都有方向）；
无向图（所有边都没有方向）；
混合图（一部分边有方向，另一部分没有）。
-
按照边是否有权：
有权图、无权图。
3. 简单图
- 自环：对于边 \((u, v)\)，若 \(u = v\)，那么 \(e\) 叫做自环。
- 重边：连接同一组顶点的边互为重边。
- 如果一个图没有自环或重边，那么这个图叫做简单图。反之，这个图叫做多重图。
4. 图的连通性
5. 图的存储
在 C++ 语言中，一般使用下列方法来存储图。
1）邻接矩阵
2）邻接表
3）链式前向星
6. 图的遍历
图一般有两种遍历方式：DFS 与 BFS。
1）DFS
2）BFS
7. 特殊的路径
1）最短路
对于一条路径，若它是节点 \(u\) 到节点 \(v\) 所有路径中，权值和最小的那条，那么这条路径叫做节点 \(u\) 到节点 \(v\) 的最短路。反之，若权值和最大，那么它叫做最长路。
最短路或最长路，可以使用多种算法求解。
A. 单源最短路
a. Dijkstra 算法
b. Bellman-Ford 算法
c. SPFA 算法
B. 多源最短路
a. Floyd 算法
b. Johnson 算法
2）环
对于一条路径，若起点与终点相同，且这组点对是唯一重复出现的点对，那么这条路径叫做一个环。
如果一个环所有边的权值为负，那么这个环叫做负环。
可以使用 SPFA 算法寻找图中负环。