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

最小生成树and最短路径无独有偶,在两个学期的期末中两门不同的科目《离散数学》和《数据结构》中都谈到了图及其衍生的最小生成树、最短路径问题,并给出了相应的算法——克鲁斯卡尔、普林、迪杰斯特拉、沃舍尔算法。这无疑是释放了一个很大的信号——这些内容很重要。由于之前学《离散数学》时只要求在思想上理解,并没要求程序实现,所以学起来也挺吃力的。而现在来到了《数据结构》的课程上,我觉得还是有必要写写理解与体会,好让以后用起来没那么难。最小生成树(MinimumSpanningTree,MST)一个有n个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有n个结点,并且有保持图连通的最少的边。即是在原图上删除边,直到剩余n-1条边,保证n个结点连通且边的权值加起来最小。简单图示:21 121 132 MST 2 54343 4 4克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法从边的角度来解决问题,即在剩下的所有未选取的边中,找最小边,如果和已选取的边构成回路,则放弃,选取次小边。然而,图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的,该方法对于边数相对比较多的图不是很实用,浪费时间。可以说克鲁斯卡尔算法是很直观的算法,适合人的直观思考方式,但是因为上面论述的缘故,克鲁斯卡尔算法比较适用在稀疏图(边的数目不是很多的图)上。边集数组:从图变为程序需要的数据,需要采用合适的数据结构。由算法的核心思想上看,我们需要存储的数据为边,而边的要素包括三点:连接的两个结点、边的权值。然而边并不需要具有什么操作来改变自身或者做些什么,所以用struct来自定义就合适不过了。structedge{ intnode_1; intnode_2; intvalue;};另外,文中提及了最小边、次小边,这就暗示了应该对所有的边进行排序(sort)。比较函数应以value作衡量。boolcmp(edgea,edgeb){   <;}现在剩余最后的问题——回路的避免。其实这个也很容易避免,我们可以定义一个数组used[max],它记录了每一个结点是否被应用的情况,当要加入的一条边中used[]和used[]都已被应用,那么加入的这条边必然造成回路,否则不会。若造成回路,则舍弃这条边,转而观察加入次小边。排序后的情况edge数组node_1node_2value01211242224333444235用红线将舍弃的边删除后,剩余的就成为了最小生成树了。时间复杂度若e表示图的边数,那么,排序过程将有O(eloge),生成过程则是O(e),故总的来说,时间复杂度为O(eloge)。普林(Prim)算法克鲁斯卡尔算法以边为出发点,相应地,普林算法则以点为出发点。从指定顶点开始将它加入集合中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通。再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中。如此下去直到全部顶点都加入到集合中,即得最小生成树。以点作为出发点很好地解决了克鲁斯卡尔算法解决边数很多的图的可怕时间复杂度的问题。边数不是制约普林算法的因素,结点才是。普林算法的简单演算步骤:(1)初始化集