关于最小生成树在面试中的考察
来源：11-11 本章小结和更多关于最小生成树问题的讨论
软件工程小白菜
2020-06-03
老师你好，请问老师知道kruskal和prim算法如果在面试中提及，通常会被如何考察吗？或者说我们在复习算法面试时，通常需要注意这两个算法的哪些方面？是否需要能手写？谢谢老师
写回答
1回答
-
据我所知，面试里考最小生成树还是比较少的，相较而言，考最短路径比较多。
我的建议如下：
其实 kruskal 的思路很简单，只不过因为一般标准库中不会有并查集，对于非竞赛同学，一般不会要求手写并查集的，所以最好能掌握：在已经给出一个并查集结构的情况下，kruskal 的思路是怎样的。
对于 Prim 算法，其实和 Dijkstra 的思路非常像。大厂如果考得算法难一些，考 Dijkstra 还是有可能的（优先队列基本在各个语言的标准库中都有）。建议和 Dijkstra 比较学习，了解二者的思路差异。
当然，如果时间特别紧，确实可以考虑将最小生成树算法的优先级调低。
继续加油！：）
212020-06-04
