图
图的含义
图是由顶点（vertice）和连接顶点的边（edge）组成的一种数据结构。
顶点（vertice）就是构成图的数据元素，表示图中的一个个节点。图中的每个顶点可以包含数据，在实际的应用中，一个顶点可能代表一个地点、一个用户、一个组织等实体。
举几个vertices的例子：
- 在社交网络图中，每个用户账号可以看成一个顶点。
- 在地图图中，一个城市可以看成一个顶点。
- 在程序流程图中，每个步骤是一个顶点。
- 在数据结构图中，每个数据元素是一个顶点。
边（edge）是连接图中顶点的线段。一个边只能连接两个顶点，可以表示两个顶点之间的关系、交互或依赖。边可以有方向也可以无方向。
例如：
- 在社交网络图中，边表示用户之间的关联关系或信息传递。
- 在地图图中，边可以表示城市之间的距离等信息。
图的相关概念：
- 顶点（vertice， vertex）：节点，表示图中的基本元素。
- 边（edge）：连接两个顶点的线段，表示两个顶点之间的关系。
- 有向图（directed graph）：边有方向的图。
- 无向图（undirected graph）：边无方向的图。
- 权（weight， cost）：边的数值，表示两个顶点之间连接的代价或关系。
- 网（network）：带权图，边上有权值。
- 度（degree）：一个顶点的边数。
- 出度（out-degree）：一个顶点出去的边的数量。
- 入度（in-degree）：一个顶点进来的边的数量。
图的存储结构（图的实现）：
- 邻接表（adjacency list）：使用链表或数组来表示每个顶点的邻接点。
- 邻接矩阵（adjacency matrix）：使用二维数组来表示图中任意两个顶点之间的连接关系。对于无向图，矩阵是对称的；对于有向图，矩阵可能不对称。
时间复杂度对比：
| 操作 | 邻接表 | 邻接矩阵 |
|---|---|---|
| 存储图 | O(V+E) |
O(V^2) |
| 添加顶点 | O(1) |
O(V^2) |
| 添加边 | O(1) |
O(1) |
| 删除顶点 | O(E) |
O(V^2) |
| 删除边 | O(V) |
O(1) |
| 判断顶点x和y是否相邻 | O(V) |
O(1) |
| 备注 | 删除顶点和边较慢,需要找到所有相关顶点和边 | 添加/删除顶点较慢,需要重置矩阵 |
图的遍历（和树结构类似）：
- 广度优先遍历（Breadth First Search （BFS））：从一个顶点开始，先访问其所有的邻接点，再依次访问这些邻接点的邻接点，以此类推，直到图中所有顶点都被访问到。
- 深度优先遍历（Depth First Search （DFS））：从一个顶点出发，沿着其中一条路径走到底，再回溯并找其他路径，直到图中所有顶点都被访问到。 DFS 有多种实现，比如前序遍历、后序遍历、中序遍历。
最小生成树（Minimum spanning tree）算法：
- 普里姆（Prim）算法
- 克鲁斯卡尔（Kruskal）算法
最短路径问题（Shortest path problem）：
- Dijkstra 算法
- Bellman–Ford 算法
