最小生成树and最短路径.doc

最小生成树and最短路径
无独有偶,在两个学期的期末中两门不同的科目《离散数学》和《数据结构》中都谈到了图及其衍生的最小生成树、最短路径问题,并给出了相应的算法——克鲁斯卡尔、普林、迪杰斯特拉、沃舍尔算法。这无疑是释放了一个很大的信号——这些内容很重要。由于之前学《离散数学》时只要求在思想上理解,并没要求程序实现,所以学起来也挺吃力的。而现在来到了《数据结构》的课程上,我觉得还是有必要写写理解与体会,好让以后用起来没那么难。
最小生成树(Minimum Spanning Tree,MST )
一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。即是在原图上删除边,直到剩余n-1条边,保证n个结点连通且边的权值加起来最小。
简单图示:
2
1
1
2
1
1
3 2 MST
2
5
4
3
4
3
4 4

克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔算法从边的角度来解决问题,即在剩下的所有未选取的边中,找最小边,如果和已选取的边构成回路,则放弃,选取次小边。然而,图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的,该方法对于边数相对比较多的图不是很实用,浪费时间。可以说克鲁斯卡尔算法是很直观的算法,适合人的直观思考方式,但是因为上面论述的缘故,克鲁斯卡尔算法比较适用在稀疏图(边的数目不是很多的图)上。
边集数组:
从图变为程序需要的数据,需要采用合适的数据结构。由算法的核心思想上看,我们需要存储的数据为边,而边的要素包括三点:连接的两个结点、边的权值。然而边并不需要具有什么操作来改变自身或者做些什么,所以用struct来自定义就合适不过了。
struct edge{
int node_1;
int node_2;
int value ;
};
另外,文中提及了最小边、次小边,这就暗示了应该对所有的边进行排序(sort)。
比较函数应以value作衡量。
bool cmp(edge a , edge b)
{
    return < ;
}
现在剩余最后的问题——回路的避免。其实这个也很容易避免,我们可以定义一个数组used[max],它记录了每一个结点是否被应用的情况,当要加入的一条边中used[]和
used[]都已被应用,那么加入的这条边必然造成回路,否则不会。若造成回路,则舍弃这条边,转而观察加入次小边。
排序后的情况
edge数组
node_1
node_2
value
0
1
2
1
1
2
4
2
2
2
4
3
3
3
4
4
4
2
3
5
用红线将舍弃的边删除后,剩余的就成为了最小生成树了。
时间复杂度
若e表示图的边数,那么,排序过程将有O(eloge),生成过程则是O(e),故总的来说,时间复杂度为O(eloge)。
普林(Prim)算法
克鲁斯卡尔算法以边为出发点,相应地,普林算法则以点为出发点。从指定顶点开始将它加入集合中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加