刷题要做图论算法吗

toughcharlie 发表于 2021-1-31 02:03
问最大流最小割我极其怀疑面试官的同事们能不能成功建模

竞赛题里很多Bipartite graph matching

会的，加油，也就bfs和dfs两类，还好，超纲的不常见，真遇上超纲的，就自认倒霉了，不值得花更多时间去研究那些。

union-find 也比较常见吧。

如果精力有限，建议准备顺序（根据性价比和面试出现频率）：
BFS > DFS > 拓扑排序 > Dijkstra
这些算法都用了还搞定不了的面试题，说实话，我面了这么多年这么多公司也拿了不少offer，还没见过。

有帮助希望能加点米。

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

变种题其实是蛮难的。拓扑排序解法不止一种，你可能是基于其中一种解法的变种，如果候选人只掌握了其他解法，自然就解不出你的变种题了。我问binary search的变种，能快速解出来的也只有四分之一，其他的就算解出来也要反反复复改很久，最后二三十分钟完成了十几行能工作代码，followup就死定了。

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

最短路还是经常问的。但是有些最短路问题其实是用dp解的。有的面试官喜欢问一个问题，用D*，followup问题是在前一题上稍微改了一下，就得用dp，还挺tricky的。

我觉得lz把图论想得太高端了，作为一个前数学专业，我能想到的图论算法是染色，strong component，Hamilton cycle之类的。但面试不可能考到上面这些，连Dijkstra近几年都不考了。
至于dfs，bfs和topological sorting，这些不应该是你学了图论才明白的话题，我学这些算法都是在学树的时候学的，毕竟图就是带环的，允许disconnected的树。
所以关于图论你唯一需要掌握的就是如何建图，如何用你熟悉的语言去表示图。

补充内容 (2021-2-1 00:00):
而且topological sorting说白了就是个变形的bfs，所以我觉得没必要整那么多名词。
bfs的用处可以扩散到level order traversal，unweighted shortest path，甚至你能从bfs变种到spfa，加个heap又是dijkstra了
dfs的优化策略，pruning，memoization，和分治，这些东西你玩熟练，你会发现这就是top down dp
bfs和dfs这两个搜索算法掌握好，自己看到题会建图建模型，应付面试是足够了

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

能不能谈一谈图的题目，怎么加follow up呢？能不能给点思路，帮助大家开拓一下思路啊？
===
update: 刚看到下面的回复了。

Euler57721 发表于 2021-1-30 08:32
竞赛题里很多Bipartite graph matching

对的。就是我怀疑不打竞赛的SDE们会不会去研究。本身这东西理论就有一点点复杂了，做题比理论更难受的多。

我感觉图论是最重要之一。DFS BFS 递归