算法面试题：图算法

1. 图的基础概念有哪些？

• 节点（顶点）和边。
• 有向图与无向图。
• 权重图与非权重图。

2. 深度优先搜索（DFS）和广度优先搜索（BFS）有什么区别？

• DFS 适合遍历所有路径或递归搜索。
• BFS 适合最短路径或逐层遍历。
• 两者常用于拓扑排序、连通分量。

3. Dijkstra 算法用于什么场景？

• 求单源最短路径。
• 适用于边权非负图。
• 时间复杂度取决于堆实现。

4. Bellman-Ford 算法有什么特点？

• 支持负权边。
• 可以检测负环。
• 相比 Dijkstra 时间复杂度更高。

5. 最小生成树有哪些算法？

• Kruskal。
• Prim。
• 适用于连接所有节点的最小权重树。

6. 你如何表示图结构？

• 邻接表：适合稀疏图。
• 邻接矩阵：适合稠密图或快速判断边是否存在。

7. 你如何处理图中环检测？

• 无向图可以用并查集或 DFS 回溯检测。
• 有向图可使用 DFS 颜色标记或拓扑排序。

8. 图算法面试常问哪些问题？

• 最短路径、连通分量、环检测。
• 最小生成树、网络流、图着色。