图的基本实现
广度优先搜索
深度优先搜索
Dijkstra算法
- 邻接表:
- 空间效率：
O(V + E)，适合稀疏图（边数远小于 V²）。
- 查询效率：查找邻居
O(1)，但检查边是否存在 O(E)。
- 动态性：易于添加/删除边，适合动态图。
- 邻接矩阵：
- 空间效率：
O(V²)，适合稠密图（边数接近 V²）。
- 查询效率：检查边是否存在
O(1)，但遍历邻居 O(V)。
- 动态性：添加/删除边需更新整个矩阵，适合静态图。
基于邻接表图的实现
基于邻接矩阵图的实现
- 原理：从起点开始，逐层访问所有邻居节点，基于队列实现，优先扩展距离最近的节点。
- 时间复杂度：
O(V + E)，其中 V 是顶点数，E 是边数。
- 空间复杂度：
O(V)，用于存储队列和访问标记。
- 优点：适合求最短路径（无权图）、层次遍历。
- 缺点：不适合深度优先探索（如递归路径）。
- 适用场景：最短路径、连通性检测、层次遍历。
广度优先搜索BFS的实现
- 原理：从起点开始，沿着一条路径深入探索，直到无法继续，然后回溯，基于栈（递归或显式栈）实现。
- 时间复杂度：
O(V + E)，其中 V 是顶点数，E 是边数。
- 空间复杂度：
O(V)，用于递归栈或显式栈。
- 优点：适合路径搜索、检测连通性、拓扑排序。
- 缺点：不保证最短路径，可能陷入无限循环（需标记访问）。
- 适用场景：迷宫问题、拓扑排序、检测环。
深度优先搜索DFS的实现
- 原理：贪心算法，从起点开始，逐步选择当前未访问节点中距离最小的节点，更新其邻居的距离，直到所有节点被访问目标节点距离确定。
- 时间复杂度：使用优先队列优化后为
O((V + E) log V)，其中 V 是顶点数，E 是边数；未优化为 O(V²)。
- 空间复杂度：
O(V)，存储距离数组和优先队列。
- 优点：适合单源最短路径，适用于非负权图。
- 缺点：不能处理负权边。
- 适用场景：网络路由、路径规划。
Dijkstra 算法