如何准备Graph题型

请教大家如何应该准备graph题型？
谢谢任何经验分享。

楼上说的很有道理。 Graph题目真的很容易准备，只要把最基础的那几个记住就好。 比如BFS需要用queue， DFS可以用Recursion可以用stack。 Topo Sort就是在BFS基础上套个indegree的东西。 Dijkstra用Heap。 MST把边的weight从小到大排序然后建图。 Union-Find只能背，我建议你面试中别写union by rank， 要是面试官想刁难你让你解释rank那部分真的是浪费时间。

最难的还是array或者考trick之类的。graph是某种意义上送分的题，用心准备就可以拿到分数，的那种。

面试遇到了要感恩！

这么说吧，Graph其实是最好准备的题，套路最明显，而且是不是Graph题一眼就能识别出来。你要做的就是准备那几个模版（DFS，BFS，Topological sorting，DSU，Dijkstra, etc.）

SoyTuPapa 发表于 2023-8-23 21:21
楼上说的很有道理。 Graph题目真的很容易准备，只要把最基础的那几个记住就好。 比如BFS需要用queue， DFS ...

谢谢。我就是这两天看那个Union-Find，Union by Rank看得头大。

purser 发表于 2023-08-23 22:42:49
谢谢。我就是这两天看那个Union-Find，Union by Rank看得头大。

union by rank没有意义，只path compression就够了

SoyTuPapa 发表于 2023-8-23 21:21
楼上说的很有道理。 Graph题目真的很容易准备，只要把最基础的那几个记住就好。 比如BFS需要用queue， DFS ...

我建议你面试中别写union by rank

这个什么意思，那union find怎么写？

Union find 没那么难，搞懂path by compression和union by rank，再把模版一背，很多graph的题迎刃而解

lz9527 发表于 2023-08-24 11:21:56
这个什么意思，那union find怎么写？

Union by rank顾名思义就是在union的时候用到，直接不考虑rank然后正常union就行。

比如union(x, y)如果xy不同组，就把y放到x里面或者x放到y里面。 不考虑哪个rank高或者低。

学习了，还是得熟记套路。