-
无向图的 api 和邻接表存储结构
首先是深度优先查找和广度优先查找,这个比较简单
衍生出来的是寻找联通分量,检测环和双色问题,这几个都是用深度优先解决的
最后是符号图,这个算是综合应用 -
有向图的 API
有向图的可达性,这个算是标记-清除的垃圾收集的底层思路
有向图的寻找环问题,这个感觉和深度遍历思路差不多
有向图的拓扑排序,这个就比较奇妙了,一个无环有向图的拓扑排序为所有顶点的逆后排序,证明比较奇怪
最后是寻找强联通风量,这个是用的算法和证明(特别是证明方法)比价炫酷和费解,名字叫 Kosaraju 算法 -
加权无向图的最小生成树
算法的基础是基于切分定理,几个算法的存储结构略有不同
Prim 算分的延迟实现和及时实现,具体的思想体会的还不是太深刻
Kruskal 算法的思路倒是好理解,只是证明方法也是有点费解
这一切的底部都是贪心算法的基础,还是需要深入理解
明天需要复习一下,可以的话写一下代码
接下来就是图的最短路径几个算法了
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于