刷题要做图论算法吗

dijrstra 的题目起码4-5道，那些说不用的估计都是工作几年的以前要求低确实没什么图的题，mst  dijstra belleman -ford  florid都是基本的算法 lc newwork delay 题号是767么（不确定） 你都写遍

需要特别注意的主要是拓扑排序，最短路径，

justin 发表于 2021-1-26 01:53
需要，但是只需要以下部分：
- BFS
- DFS

207过于真实...想请教一下这题可以怎么变种？

你碰上做图数据库的组来的面试官，把你烤出翔。。。基本的还是要会，高深的就没法coding了，只能当系统设计考察

Mag2679 发表于 2021-1-25 11:08
207过于真实...想请教一下这题可以怎么变种？

比如topological sorting的过程中，还需要额外去统计边或者点的权重，作为最后返回的值之类的。是需要真的对于topological sorting的应用场景有一些了解的，才知道怎么去写，而不是像course schedule一样原题默写十分钟就完事了。
细节就不说了，说多了就变成泄题了 lol

好帖马住！总结下：
must to-do:
bfs, dfs, topological sort (理解每类应用场景）

highly recommended:
shortest/minimal path (Dijkstra, Bellman-ford)
minimum spanning tree (Krusgal, Prim??)

图论很多大厂都是会考的，当然值得刷。但是图论难的不是算法本身，而是建图，也就是怎么看出某道题是图论题、应该怎么建模、用什么图算法等等。

建议图问题熟悉基本算法以后不要按照tag刷，比如你刷拓扑排序tag下的题，你都提前知道这些题要用拓扑排序了，其实就已经把最难的（也是最有价值的）部分跳过了，怎么看出这道题用拓扑排序、怎么建图让它能套上拓扑排序才是最难和最考查实力的。

yes     

Euler57721 发表于 2021-1-25 06:19
只需要学到拓扑排序就可以了，极少有面试官问最短路和最小割。

问最大流最小割我极其怀疑面试官的同事们能不能成功建模