图

简介

图是一种非线性数据结构，由顶点（节点）和边组成。图可以表示多对多的关系，是最灵活的数据结构之一。在现实世界中，图被广泛应用于社交网络、地图导航、网络拓扑等领域。

基本概念

1. 顶点（Vertex）：图中的节点，可以存储数据
2. 边（Edge）：连接两个顶点的线段，可以是有向或无向的
3. 有向图与无向图
   • 有向图：边有方向，如社交网络中的关注关系
   • 无向图：边无方向，如城市之间的道路连接
4. 权重图：边上带有权重值，表示两个顶点之间的关系强度
5. 路径与环
   • 路径：从一个顶点到另一个顶点经过的边的序列
   • 环：起点和终点相同的路径

图的表示方法

1. 邻接矩阵

   • 使用二维数组表示顶点之间的连接关系
   • 空间复杂度：O(V²)，V为顶点数
   • 适合稠密图（边数接近顶点数的平方）
   • 优点：查找、修改边的操作效率高
   • 缺点：空间占用大，不适合稀疏图

2. 邻接表

   • 每个顶点维护一个链表，存储与其相连的顶点
   • 空间复杂度：O(V+E)，V为顶点数，E为边数
   • 适合稀疏图（边数远小于顶点数的平方）
   • 优点：空间效率高，适合大多数实际应用
   • 缺点：查找特定边的效率较低

常见算法

1. 图的遍历
   • 深度优先搜索（DFS）：沿着一条路径一直探索到底，适合搜索目标路径
   • 广度优先搜索（BFS）：逐层遍历所有节点，适合寻找最短路径

2. 最短路径
   • Dijkstra算法：解决单源最短路径问题，适用于非负权重图
   • Floyd算法：解决多源最短路径问题，可处理负权重边
   • Bellman-Ford算法：可处理负权重边，能检测负权重环

3. 最小生成树
   • Prim算法：基于顶点构建最小生成树，适合稠密图
   • Kruskal算法：基于边构建最小生成树，适合稀疏图

应用场景

1. 社交网络

   • 好友关系网络
   • 推荐系统
   • 影响力分析

2. 地图导航

   • 最短路径规划
   • 交通流量分析
   • 路线优化

3. 网络拓扑

   • 网络规划
   • 路由选择
   • 网络可靠性分析

4. 任务调度

   • 项目依赖管理
   • 工作流程优化
   • 资源分配