图
一种多对多数据结构。用 表示， 表示一个顶点集， 表示一个边集。
根据边的类型分类：
- 有向图，用 表示一条有向边
- 无向图，用 表示一条无向边
根据复杂度：
- 简单图：1. 不存在重复边；2. 不存在顶点到自身的边；
- 复杂图：允许重复边也允许顶点到自身的边；
完全有向图：每对顶点之间都存在两条反向的有向边； 完全无向图：每对顶点之间都存在一条无向边；
连通与否：
- 连通图：任意两个顶点之间相互连通（即通过一定路径可以到达）；
- 非连通图：存在不可达的顶点对；
连通分量：无向图的极大连通子图，再加入任何一个顶点均不连通； 强连通图：有向图中每个顶点均存在双向路径（即 可以到 ， 也可以到 。） 弱连通图：有向图中任意两个顶点均有边，不管方向；
一些基础概念
- 度：依附于顶点的边数叫做顶点的度，无向图的总度等于边数的两倍，有向图一个结点的度等于出度加入度，总入度等于总出度等于边数；
- 权、网：权是边上具有某种含义的数值，带权图又被称为网；
- 稠密图和稀疏图：一般当图 满足 时，可以将 视为稀疏图；
- 有向树：一个顶点入度为 0 ，其余顶点入度均为 1 的有向图，称为有向树；
存储方式
- 邻接矩阵（二维数组）
- 邻接表（链表）
遍历方式
- 深度优先遍历（DFS）
- 广度优先遍历（BFS）
图的相关应用
最小生成树
- Prim 算法
- Kruskal 算法
最短路径算法
- Dijkstra 算法
- Floyd 算法
算法思想都是按照递增顺序查找最短路。
无权图单源最短路算法
使用广度优先遍历（BFS）即可，注意访问标志数组变成了最短距离数组 dist[] ，增加路径数组 path[] 存储从 到 的路径。
有权图单源最短路算法
初始化 dist[] 为全部无穷大的数组，用于存放图的最短路径数值，先将起点的 dist[s] 定义为 0。然后每次从 dist[] 中选择路径最小的点，将其标记为 collected[] = true 表示放进了确定最小值的顶点集合中。然后遍历他的所有邻接点并更新邻接点的 dist[] 值和前置顶点 path[] 数组。经过寻找，直到所有的点都被收集进了确定最小路径的顶点集合 collected[] 中。算法结束。