高级算法日记12:图(5)
作者：孙相国
contact：[email protected]
版权所有，禁止任何商业用途和转载。
从本篇博文开始，我们会用大概5篇文章的长度，来系统性地讲解数据结构中的图论。我们期望达到的目标是比你在本科理解的更深入。
下面这些，是我讲授数据结构和高级算法的一部分课件，讲课的视频可以见下面的这个链接
http://player.youku.com/player.php/sid/XMjg3OTk4OTYyOA==/v.swf
点击此链接即可免费直接播放。
内容提要
本篇博文承接上一篇博文
讲授内容有：
最小生成树
树图/连通图/连通分量
强联通图/强联通分量
支撑子图/支撑树/最小支撑树
为什么要研究最小支撑树
通用贪心算法
kruskal算法
Prim算法
割/交叉边/最小交叉边/割与图的交集/尊重
安全边
kruskal和prim算法的本质
三种割（割权值最小边/割邻居/瞎割）
kruskal与prim代码实现与复杂度分析
最宽路径问题
最短路径的基本概念（源点可达负回路，简单路径，松弛操作）
一些练习题
手机扫一扫，即可：