本页面全面概述了技术面试中常见的图算法。图算法是算法知识的重要组成部分，尤其适用于解决与网络、连接和遍历相关的问题。本指南涵盖了遍历技术、最短路径算法和最小生成树算法，包括它们的实现和时间复杂度。
有关用于表示图的数据结构的信息，请参阅树和图。
在深入探讨图算法之前，了解图如何在代码中表示非常重要。
| 表示方式 | 空间复杂度 | 检查边是否存在 | 遍历边 | 最适合 |
|---|---|---|---|---|
| 邻接矩阵 | O(V²) | O(1) | O(V²) | 稠密图 |
| 邻接表 | O(V + E) | O(degree) | O(V + E) | 稀疏图 |
| 边列表 | O(E) | O(E) | O(E) | 需要边操作的算法 |
来源: README.md:175-186
图遍历是访问图中所有顶点的过程。两种基本的图遍历算法是深度优先搜索（DFS）和广度优先搜索（BFS）。
深度优先搜索在回溯之前会沿着每条分支尽可能深地探索。它使用一个栈（通常通过递归实现）来跟踪要探索的顶点。
时间复杂度：O(|V| + |E|)，其中 V 是顶点数，E 是边数。
应用程序:
来源: README.md:232-236
广度优先搜索在移动到下一深度级别的节点之前，会探索当前深度的所有邻居节点。它使用一个队列来跟踪要访问的顶点。
时间复杂度：O(|V| + |E|)，其中 V 是顶点数，E 是边数。
应用程序:
来源: README.md:238-242
最短路径算法寻找图中顶点之间成本（距离、时间等）最小的路径。
Dijkstra 算法用于查找图中边权重为非负数的节点之间的最短路径。
时间复杂度：使用优先级队列的数组实现时为 O(|V|²)。使用二叉堆实现时为 O((V+E)log V)。
应用程序:
来源: README.md:250-252
Bellman-Ford 算法计算加权图中从单个源顶点到所有其他顶点的最短路径，即使存在负边权重也能处理。
时间复杂度:
O(|E|)O(|V||E|)应用程序:
来源: README.md:257-262
Floyd-Warshall 算法在带有正或负边权重（但没有负环）的加权图中查找所有顶点对之间的最短路径。
时间复杂度：所有情况下均为 O(|V|³)。
应用程序:
来源: README.md:266-273
最小生成树（MST）是连通无向图的边的子集，它连接所有顶点，且总边权重尽可能小。
Prim 算法是一种贪婪算法，用于查找加权无向图的最小生成树。
时间复杂度：使用数组实现时为 O(|V|²)。使用二叉堆时为 O(E log V)。
应用程序:
来源: README.md:275-278
Kruskal 算法也是一种用于查找最小生成树的贪婪算法，但它的工作原理是排序所有边，然后如果它们不形成环则逐渐添加它们。
时间复杂度：由于排序步骤，为 O(|E|log|V|)。
应用程序:
来源: README.md:282-286
有向图的拓扑排序或拓扑顺序是其顶点的一种线性排序，使得对于每条有向边 (u, v)，顶点 u 在排序中都出现在 v 之前。
时间复杂度：O(|V| + |E|)
应用程序:
来源: README.md:245-248
图算法在技术面试中经常被考查。以下是一些常见的问题类型：
连通性问题
路径查找问题
环检测
图着色和二分图检查
网络流问题
特殊图问题
来源: README.md:230-286
在面试中实现图算法时，请考虑以下几点：
图表示方式的选择:
访问跟踪:
队列/栈实现:
边界情况:
性能优化:
来源: README.md:175-286
该存储库包含多个图问题的实现示例。虽然不涵盖所有图算法，但这些示例展示了如何应用图概念来解决问题。
来自 BreadthFirstSearch 文件夹
来自 DepthFirstSearch 文件夹
来源: README.md:416-431
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 深度优先搜索（DFS） | O(V + E) | O(V) |
| 广度优先搜索 (BFS) | O(V + E) | O(V) |
| 拓扑排序 | O(V + E) | O(V) |
| Dijkstra 算法 | O(V²) 或 O((V+E)log V) | O(V) |
| Bellman-Ford 算法 | O(V·E) | O(V) |
| Floyd-Warshall 算法 | O(V³) | O(V²) |
| 普里姆算法 | O(V²) 或 O(E log V) | O(V) |
| 克鲁斯卡尔算法 | O(E log V) | O(V) |
来源: README.md:232-286