最小生成树与最短路径问题

《最小生成树与最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图——最小生成树与最短路径问题2009/05/14基于邻接表的图操作运算2基于邻接表的图操作运算34主要内容生成树的概念（spanningtree）Prim算法Kruskal算法最短路径问题Dijkstra算法Floyd算法5生成树（支撑树）的概念GraphMatrixgraph={6,{{0,10,M,M,19,21},{10,0,5,M,M,11},{M,5,0,M,M,M},{M,M,M,0,18,14},{19,M,M,18,0,33},{21,11,M,14,33,0}}};012345子图+连通+无环6无向图中无环的充要条件检查每一个连通分枝对

2、于所有连通分枝：顶点数–边的数目=1可以采用周游算法。算法复杂度：n0123457最小生成树Minimum-costSpanningTree连通无向带权图——网络。网络（带权图）的生成树中生成树各边的权值加起来称为生成树的权，把权值最小的生成树称为最小生成树。(简称为MST)。8G=(V，E)是一个网络，U是顶点集合V的一个真子集。如果u∈U，v∈V-U，且边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边，则一定存在G的一棵最小生成树包括此边(u,v)。MST必包含连通图中任意两个顶点划分之间的最小权的边。（任意割集中的最小边）

3、MST性质9MST性质证明（反证法）uu´vv´UV-Uvv边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边。假设：存在G的一棵最小生成树不包括此边。10Prim算法（找MST）prim算法的基本思想是∶首先从集合V中任取一顶点(例如取顶点v0)放入集合U中这时U={v0}，TE=NULL然后在所有一个顶点在集合U里，另一个顶点在集合V-U里的边中，找出权值最小的边(u,v)(u∈U，v∈V-U)，将边加入TE，并将顶点v加入集合U重复上述操作直到U=V为止。这时TE中有n-1条边，T=(U，TE)就是G的一棵最小生成树11最

4、小生成树的构造准备工作：设图采用邻接矩阵表示法表示，用一对顶点的下标(在顶点表中的下标)表示一条边，定义如下∶在构造最小生成树的过程中定义一个类型为Edge的数组mst∶Edgemst[n-1];其中n为网络中顶点的个数，算法结束时，mst中存放求出的最小生成树的n-1条边。typedefstruct{intstart_vex,stop_vex;/*边的起点和终点*/AdjTypeweight;/*边的权*/}Edge;12例子：mst∶Edgemst[n-1];已知带权图G及其邻接矩阵如图所示请构造该图的最小生成树úúúúúúúúûùêêêêêêêêëé

5、¥¥¥¥¥¥¥¥¥¥033141121330181914180666051165010211910013n=6，只有顶点v0在最小生成树中。mst[5]={{0,1,10},{0,2,∞},{0,3,∞},{0,4,19},{0,5,21}}在mst[0]到mst[4]中找出权值最小的边mst[0]，即(v0,v1)，将顶点v1及边(v0,v1)加入最小生成树。úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥03314112133018191418066605116501021191001n-114n=6，只有顶点v0在最小生成树中。mst[5

6、]={{0,1,10},{0,2,∞},{0,3,∞},{0,4,19},{0,5,21}}在mst[0]到mst[4]中找出权值最小的边mst[0]，即(v0,v1)，将顶点v1及边(v0,v1)加入最小生成树。调整：mst[5]={{0,1,10},{1,2,5},{1,3,6},{0,4,19},{1,5,11}}úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥03314112133018191418066605116501021191002n-2比较15mst[5]={{0,1,10},{1,2,5},{1,3,6},{3,4,18},

7、{1,5,11}}mst[5]={{0,1,10},{1,2,5},{1,3,6},{3,4,18},{1,5,11}}úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥03314112133018191418066605116501021191003n-316mst[5]={{0,1,10},{1,2,5},{1,3,6},{1,5,11},{3,4,18}}17调整为成新边18Prim算法时间复杂度Prim算法的时间主要花费在选择最小生成树的n-1条边上。外循环执行n-1次，内循环两个，时间耗费为：整个算法的时间复杂度为O(n2)19贪心算法

8、一般思路初态（起点）候选对象集合贪心选择算法（按当前状态）可行评估