图的基础算法(四) -- 图的表示和拓扑排序

[@alexbordon8886]

讲的内容跟我自己总结的graph的算法几乎一模一样！但我可是积累了好几年。很赞! 早看到你们视频就好了。

[@古城算法]

感谢支持！你已经很熟练拉！

[@mengyugao8050]

谢谢前辈的讲解。讲的很好！

[@ExplosionBobXD]

希望UP主继续更新呀，你讲的真的挺好的学到很多。

[@古城算法]

感谢支持，我们每周五还有直播。视频都会上传

[@zewang625]

感谢博主，非常有帮助

[@zhiyongchen1638]

讲得真好，本科时候总是不理解dfs怎么查环，现在有bfs 这种直观易理解的方法真不戳🤠

[@Bearbearguan]

讲得好棒

[@古城算法]

哈哈哈，感谢支持！

[@boyuanchang8708]

好人一生平安🙇‍♂

[@古城算法]

哈哈，你也是！感谢支持~

[@hermine7744]

想请教，如果需要打印出所有的可能性，又该怎么做呢？

[@DED_Search]

悦少，想问两个问题，比较困扰 1. topological sort的两种方法，可以用来判断directed graph是否有环，对吧？ 2. 如果是undirected graph, 用什么方法可以判断是否有环呢（a -> b -> a这种的除外)? graph coloring的方法就不能用了么？bfs + visited set + coloring 行么？谢谢

[@古城算法]

无向图也可以使用拓扑，或者直接使用并查集，如果并查集两个merge点parent相同则是环。 拓扑则小变化一点，从入度为1的点进去，跑一次拓扑排序，如果还有点degree是1就会成环

[@古城算法]

虽然几乎考不到，但是感觉也可以出一期专门研究下。

[@SmallSun0059]

37分钟那个人想问的是，如果外面单独有两个课，比如前面循环里有一些课1234之类的，然后突然冒出来俩课，[100, 102]，跟谁也不挨着，他想问的是这时候是否也算能上完全部课程。答案是是的，因为102的入度也是0，上完102会解锁100，然后100的入度也变为0了。所以他们是会进入while循环的。那个人的担心是这俩单独的课不进循环，那么总课程数怎么会减为0呢。他忽略了，这个简单的事实，单独的课也会出现入度为0的。会进入循环，放心。

[@古城算法]

感谢信息！

[@nanliang2237]

hello, 老师， 昨天敲了一段代码 207 bfs的, 但是有一个例子超时了， 但是dfs 没有，是不是处理某些极端use case 时，他们还是有区别的？三色法时间还不错 class Solution { public: bool canFinish(int numCourses, vector& prerequisites) { graph_ = vector (numCourses); for(const auto& p: prerequisites) { const int start = p[1]; const int end = p[0]; graph_[start].push_back(end); } vector status (numCourses, 0); //0 unvisited , 1, visiting, 2 visited for(int i = 0; i < numCourses; i ++) { if(dfs(i, status)) return false; } return true; } private: vector graph_; bool dfs(int cur, vector& status) { if( status[cur] == 1) return true; if( status[cur] == 2) return false; status[cur] = 1; for(const int t: graph_[cur]) { if(dfs(t, status)) return true; } status[cur] =2; return false; } };

[@古城算法]

207不可以用bfs把，直接用拓扑不会超时啊kahn's algorithm. BFS写法

[@nanliang2237]

@@古城算法 我说错了，就是这个算法的BFS写法

[@gabrielxu2087]

topological sorting: bfs -> Kahn; dfs -> 3-color. 但感觉大家更常用的还是Kahn；如果不是面试官一定要我用三色法，我估计也不太去用。

[@古城算法]

是的是的，Kahn更常见

[@frederickbarbarossa2746]

36:39 第55行 res 这个array最后存的顺序是倒序的吗？

[@古城算法]

对的呢

[@frankzeng7923]

请问一下，在course schedule ii这道题里，如果每个course还有一个priority，而且我们想在保证顺序的情况下先上high priority的课，那这样dfs拓扑排序应该怎么改呢？

[@dr_920]

是不是可以搞个priority queue，搞一个pair，入度和你的priority，假设有一堆入度为0的点，优先级大的会在队顶，先拿出来。

[@SmallSun0059]

@@dr_920 同意，在原来随便放的情况下，改为有个优先级放，deque可能要改为heap了。

[@weiyao806]

请问周五实时上课，有没有课表呢？是否可以提前知道上课内容，以便于准备。

[@古城算法]

有的呢呀，加群就好

[@古城算法]

如果需要群的话，加机器人wechat: cc150pass

[@古城算法]

kzbin.info%E5%8F%A4%E5%9F%8E%E7%AE%97%E6%B3%95/about

[@benyao788]

可以把slides分享一下吗

[@古城算法]

在youtube about页面有的呢

[@benyao788]

@@古城算法 感谢回复，看到了

[@Ghost223Clifford]

这是一个网课的录频吗？听到后面还有人提问😀

[@古城算法]

对，是zoom直播。

[@haotianxue4702]

想问一下，35:27 图中的48行是否应该return res的倒序呢?

[@古城算法]

并不是，edge本身给的时候是[1->0],是先上0再上1， 我们图里面也是1->0,然后先遍历0，后遍历1

[@haotianxue4702]

@@古城算法 好的我明白了 谢谢！

[@xiaoxiaoxiao2043]

我也是在这里卡住了，后面发现UP主造图的时候是反着造的，所以DFS 逆后序就直接变后序了，这好种做法好大佬

[@eddiedu3725]

Eddie, DFS 搜索法上那些element顺序其实也不是非得从5节点开始“反方向”遍历吧，您只讲了post order dfs graph traversal, 我看其他视频上都是preorder DFS traversal, 这顺序其实是正方向的kzbin.info/www/bejne/n5Kldn6latiAbdk，麻烦澄清下，谢谢！

[@古城算法]

这个只取悦于你在进stack之前还是出stack的时候标记visit，只要改变标记的位置就可以实现正反。

[@eddiedu3725]

@@古城算法 谢谢老师

[@weiyao806]

这个三色法讲解的比leetcode上solution清晰，我看leetcode就没看下去，这个DFS一下子就明白了。

[@古城算法]

哈哈，感谢感谢。我也是neu算法课听老师讲的