Graph

无向图找两点间的path:无向图搜索就是DFS/BFS + visited set
有向图找两点间的path:如果有向图可能有环，我们也一样需要使用visited set，只不过这里我们不care edge只care node，所以visited set应该记录的是node信息。
check有向图是否有环：这道题我们可以使用三种方法
- 拓扑排序：只有最后形成的path包含了每一个node，才是没有环
- DFS/BFS：这里我们用一个globally visited set来记录我们已经遍历过的node，然后一个temp visited set来记录当下recursion stack里visited过的，重复就说明有环。
- 3-color painting。还是使用DFS/BFS，只不过开始都是白色，当下recursion的时候涂成灰色，如果遇到了灰色again，那么说明有环。如果没有遇到，再遍历一遍全部涂成黑色。
check无向图是否有环：这里我们有两种办法
- union-find：使用union-find我们可以check到每一条edge的情况。这样只要两个node在union之前已经连上了，则说明有环
- DFS/BFS：和有向图不同的是，如果只有两个node相连，那么他们是不叫环的。但是我们使用BFS/DFS的时候，在a->b之后，又会check b->a，所以我们要记录parent.只有当neighbor已经visited过并且还不是parent，说明我们找到了环。

有向图是否有环

无向图是否有环

无向图是否有环无向图找两点间path

有向图找两点间path

无向图遍历

results matching ""