关于最小生成树在面试中的考察

Question

老师你好，请问老师知道kruskal和prim算法如果在面试中提及，通常会被如何考察吗？或者说我们在复习算法面试时，通常需要注意这两个算法的哪些方面？是否需要能手写？谢谢老师

Answer 1

liuyubobobo 2020-06-04 02:19:24

据我所知，面试里考最小生成树还是比较少的，相较而言，考最短路径比较多。

我的建议如下：

其实 kruskal 的思路很简单，只不过因为一般标准库中不会有并查集，对于非竞赛同学，一般不会要求手写并查集的，所以最好能掌握：在已经给出一个并查集结构的情况下，kruskal 的思路是怎样的。

对于 Prim 算法，其实和 Dijkstra 的思路非常像。大厂如果考得算法难一些，考 Dijkstra 还是有可能的（优先队列基本在各个语言的标准库中都有）。建议和 Dijkstra 比较学习，了解二者的思路差异。

当然，如果时间特别紧，确实可以考虑将最小生成树算法的优先级调低。

继续加油！：）

• 提问者 软件工程小白菜 #1

  感谢老师的建议！