最小树最短路以及动态规划思想

图第二讲

——最小树最短路以及动态规划思想胡俊峰2011/05/25123Seamcarving算法原理一、分析图像中各区域的“重要程度”（能量函数）二、不断寻找能量最小的路径（Seam），将它Carve掉4能量函数SeamCarving采用的能量函数：图像的梯度信息e(I)=abs(I/x)+abs(I/y)即，图片中色彩反差大的地方，很可能是图片重点区域的边缘。5寻找能量最小的路径Seam路径：贯穿左右（上下）每向右一格，向上向下最多偏移一个像素（是否可以改进？）n2时间的动态规划的算法M(i,j)=e(i,j)+min(M(i−1,j−1),M(i−1,j),M(i−1,j+1))找到Seam后将它去掉，然后图片左右（上下）两部分合并678Seamstretching91011121314主要内容生成树的概念（spanning

tree）Prim算法Kruskal算法最短路径问题Dijkstra算法Floyd算法动态规划思想15图的生成树基本概念：针对对象-连通的无向图或强连通的有向图对于连通的无向图，从任一顶点出发，可以访问到所有的顶点。周游时经过的边加上所有顶点构成了图的一个连通子图，称为图的一个生成树。它含有图中的全部n个顶点，但只有足以构成一棵树的n-1条边，是连通图的一个极小连通子图。16生成树（支撑树）的概念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} }};

0

1

2

3

4

5子图+连通+无环17无向图中无环的充要条件检查每一个连通分枝对于所有连通分枝：顶点数–边的数目=1可以采用周游算法。算法复杂度：n

0

1

2

3

4

518最小生成树Minimum-costSpanningTree连通无向带权图——网络。网络（带权图）的生成树中生成树各边的权值加起来称为生成树的权，把权值最小的生成树称为最小生成树(简称为MST)。

19G=(V，E)是一个网络，U是顶点集合V的一个真子集。如果u∈U，v∈V-U，且边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边，则一定存在G的一棵最小生成树包括此边(u,v)。MST必包含连通图中任意两个顶点划分之间的最小权的边。（任意割集中的最小边）MST性质（prim算法原理）20MST性质证明（反证法）uu´vv´UV-Uvv边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边。假设：存在G的一棵最小生成树不包括此边。21Prim算法（找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的一棵最小生成树22最小生成树的构造准备工作： 设图采用邻接矩阵表示法表示，用一对顶点的下标(在顶点表中的下标)表示一条边，定义如下∶在构造最小生成树的过程中定义一个类型为Edge的数组

mst∶Edgemst[n-1];

其中n为网络中顶点的个数，算法结束时，mst中存放求出的最小生成树的n-1条边。typedef

struct{

int

start_vex,stop_vex;/*边的起点和终点*/

AdjTypeweight; /*边的权*/}Edge;23例子：mst∶Edgemst[n-1];已知带权图G及其邻接矩阵如图所示请构造该图的最小生成树úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥033141121330181914180666051165010211910024n=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-125n=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)加入最小生成树。调整：mst[5]={{0,1,10},{1,2,5},{1,3,6},{0,4,19},{1,5,11}}úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥03314112133018191418066605116501021191002n-226mst[5]={{0,1,10},{1,2,5},{1,3,6},{3,4,18},{1,5,11}}mst[5]={{0,1,10},{1,2,5},{1,3,6},{3,4,18},{1,5,11}}úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥03314112133018191418066605116501021191003n-327mst[5]={{0,1,10},{1,2,5},{1,3,6},{1,5,11},{3,4,18}}28Prim算法时间复杂度Prim算法的时间主要花费在选择最小生成树的n-1条边上。外循环执行n-1次，内循环两个，时间耗费为：整个算法的时间复杂度为O(n2)29贪心算法（一般思路）初态（起点）候选对象集合贪心选择算法（按当前集合分割状态）可行评估函数（找出最小变）目标函数（V–U=O）30Kruskal算法设G=(V，E)是网络，最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，φ)，T中每个顶点自成为一个连通分量。将集合E中的边按权递增顺序排列，从小到大依次选择顶点分别在两个不同连通分量中的边加入图T，则原来的两个连通分量由于该边的连接而成为一个连通分量。依次类推，直到T中所有顶点都在同一个连通分量上为止，该连通分量就是G的一棵最小生成树。

31例题∶用Kruskal方法构造图的最小生成树集合E中的边按权递增顺序排列为∶

(v1,v25),(v1,v36),(v2,v36),(v0,v110),(v1,v511),(v3,v514),(v3,v418),(v0,v419),(v0,v521),(v4,v533)32

①初始时，T为只有6个顶点的非连通图。②边(v1,v2)的两个顶点v1，v2分别属于两个连通分量，将边(v1,v2)加入T。③同理，将边(v1,v3)加入T。④由于边(v2,v3)的两个顶点v2，v3属于同一个连通分量，因此，舍去这条边。⑤同理将边(v0,v1)、(v1,v5)加入T，边(v3,v5)舍去，边(v3,v4)加入T。这时T中含的边数为5条，成为一个连通分量，T就是G的一棵最小生成树。3334算法框架T=(V,φ)

while(T中所含边数<n-1)

{

从E中选取当前最短边(u,v)；

从E中删去边(u,v)；

if((u,v)加入T中后不产生回路)

将边(u,v)加入T中；

}

35算法复杂度O(eloge)36最短路径问题如果图中从一个顶点可以到达另一个顶点，则称这两个顶点间存在一条路径。从一个顶点到另一个顶点间可能存在多条路径，而每条路径上经过的边数并不一定相同。如果图是一个带权图，则路径长度为路径上各边的权值的总和，两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径，其路径长度称为最短路径长度。37Dijkstra算法

——SingleSource/AllDestinationsDijkstra算法求解从顶点v0出发到其它各顶点最短路径。01234567SanFranciscoDenverChicagoBostonNewYorkMiamiNewOrleansLosAngeles300100080012001500140010009001700100025038基本思想设置一个集合U，存放已求出最短路径的顶点，V-U是尚未确定最短路径的顶点集合。每个顶点对应一个距离值，集合U中顶点的距离值是从顶点v0到该顶点的最短路径长度；集合V-U中顶点的距离值是从顶点v0到该顶点的只包括集合U中顶点为中间顶点的最短路径长度。39初始状态：集合U中只有顶点v0，顶点v0对应的距离值为0，集合V-U中顶点vi的距离值为边(v0,vi)(i=1,2,…,n-1)的权，如果v0和vi间无边直接相连，则vi的距离值为∞。40处理框架：（1）在集合V-U中选择距离值最小的顶点vmin加入集合U；（2）对集合V-U中各顶点的距离值进行修正：如果加入顶点vmin为中间顶点后，使v0到vi的距离值比原来的距离值更小，则修改vi的距离值。（3）重复（1）（2）操作，直到从v0出发可以到达的所有顶点都在集合U中为止。41存储结构图采用邻接矩阵表示法，其中对角线元素初值均取0。算法中，将放入集合Ｕ中结点对应的关系矩阵中对角线元素值修改为1；设置一个数组dist，dist[ｉ]用于存放v0到顶点vｉ的最短路径及其最短路径长度（计算过程中为距离值）∶

ypedef

struct{

AdjTypelength; /*最短路径长度*/

int

prevex; /*从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点*/}Path;Path*dist;42修正距离值的方法如果加入顶点vmin为中间顶点后

dist[i].length>dist[min].length+G.arcs[min][i]则将顶点vi的距离值改为

dist[min].length+G.arcs[min][i]并修改路径上vi的前趋顶点：

dist[i].prevex=min43例子：初始状态V={v0}结果dist[n]为{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}44②．在集合V-U中找出距离值最小的顶点v2，将顶点v2加入集合U中。