5.4图的应用

5.4图的应用

图的应用

1.最小生成树（研究问题：个村庄修路连通，怎样花销最小让个村庄连通）

一个连通图的生成树是该图的极小连通子图，通常为带权无向图

包含所有顶点，尽量少的边。

删除一条边则变为非连通图，增加一条边则会产生回路。

特点：

1.最小生成树不唯一，但该无向连通图中无相同权值边则最小生成树唯一；

2.最小生成树的权值之和唯一，即代价唯一；

.该树顶点数为该连通图结点个数n，所有该生成树边为n-1。

常用生成树算法：

1.prim算法

2.Kruskal克鲁斯卡尔算法

两种算法都属于贪心算法。这也说明了生成树不唯一。

注：带权连通图的任一一个环中所包含的权值均不相同（充分不必要条件），则最小生成树唯一；

1.1prim算法

1.初始结点并加入顶点集U中；

2.遍历顶点集U中顶点，取指到向下一顶点的权值最小边且不造成回路，并将该下一顶点加入顶点集；

.循环2直到所有顶点加入顶点集。

//V为结点集合
void Prim(G,T){T=null;U={v1};while(U!=V){edge,next_v =find_min_nextnode(U,V-U);//到U中顶点到V-U中顶点最小边T=edge;//该边加入最小生成树U=next_v;//对应结点加入U集合}
}
//时间复杂度O(V^2),不依赖E

[外链图片转存失败(img-I4qbXAVm-156872822107)(F:\Tim\1094201572\MobileFile\IMG_20190905_22948__01.jpg)]

1.2Kruskal算法

1.初始化所有边为堆

2.堆查最小权值边，且不构成回路；并在堆集合删除该边；故选择最小权值边时间复杂度为O(logE)

.循环2直至连通分量数为0，也就是T中边树为n-1;

//按权值递增的次序选择小而合适的边构造最小生成树
void Kruskal(G.V,T){T = V;numS = n;//连通分量数while(numS > 1){min_e = find_min_E(E);if(该边在剩余堆集合中会构成回路){T=min_e;numS--;}}
}

[外链图片转存失败(img-aCDU6QM-156872822109)(F:\Tim\1094201572\MobileFile\IMG_20190905_22404__01.jpg)]

1.破圈法

最短路径一定为简单路径，即路径中结点不重复。

对于无权图而言，两点之间边数最少的路径为最短路径；可用广度优先搜索查最短路径；

对于有权图（可有向可无向），两点之间带权路径最短的为最短路径；

求解有权图最短路径的算法：

Dijkstra迪杰斯拉算法：求带权有向图的指定某一顶点到其他个个顶点的的最短路径，即求单源最短路径；

Floyd弗洛伊德算法：求带权有乡土所有顶点的之间的最短路径；

2.1Dijkstra算法

求某一顶点到其他个个顶点的的最短路径，即求单源最短路径；算法基于贪心策略，主体部分为一个双重循环，时间复杂度为O(V^2),

若要使用Dijkstra求解所有顶点之间的最短路径则指定V每一结点各使用一便Dijkstra算法。时间复杂度为O(V^)，故dijkstra认为可以求解每对顶点之间的最短路径问题

注：Dijkstra不适用带负权值的图

算法思想：

集合S,先后顺序存放求得最短路径的结点

1）初始化：S={0}，0为V0源点结点,dist[i] =G.arcs[0]i]，i=1,2,… //V0到Vi结点的当前最短距离，限制为1步；

2）从V-S中选出结点Vj,Vj=Min{dist[i]|Vi属于V-S中}，选取当前限制步速到达结点中距离最短的结点加入S集合中,S=S{j},即该轮得到最短路径的结点

）限制步速1，更新使V0结点限制步速到达任一结点的最短路径，dist[j]G.arcs[j]k]<dist[k].则更新dist

4)重复2））操作n-1轮，直到所有结点包含在S中

注：Dijkstra求最短路径的“权值最小”和prim求最小生成树的“权值最小”的区别

Prim求最小生成树的“权值最小”是U集合中点到V-U集合中点的最小权值边；

最小生成树问题的图为带全无向图。 ·

而Dijkstra求最短路径的“权值最小”是源点到结点的的路径权值最小，即始终相对于选取的原点V0限制步速到指定结点的路径之和权值最小。

最短路径问题的图可为无向也可为有向。

最短路径例题：

[外链图片转存失败(img-gUxRCug5-156872822110)(F:\Tim\1094201572\MobileFile\Dijkstra_example.jpg)]

Dijkstra算法过程：

[外链图片转存失败(img-hHTE9DI-156872822111)(F:\Tim\1094201572\MobileFile\Dijkstra_example2.jpg)]

依次求出1到5，4，2，的最短路径

1-5：5；

1-5-4：7；

1-5-2：8；

1-5-2-：9；

2.2Floyd算法

算法描述：

定义个n阶方阵序列A(-1),A(0),…,A(n-1),其中A(-1)为初始图 的邻接矩阵arcs[i]-[j]；

A(k)[i]-[j] = Min{A(k-1)[i]-[j],A(k-1)[i]-[k]A(k-1)[k]-[j] }

时间复杂度为O(V^).

Floyd允许图中带负权值的边，但不允许负权值边构成回路。而Dijkstra不适用带负权值的图。

[外链图片转存失败(img-VTf7jDAX-156872822124)(F:\Tim\1094201572\MobileFile\floyd.jpg)]

求解AOV网问题，有向无环图DAG图，顶点表示活动，边表示活动与活动之间存在联系；

金典研究问题：学生专业选课，顶点为课程，边为课程之间的关系，先修什么再修什么，拓扑排序给出结果,

即需要先完成什么才能继续干什么；

算法思想：

1.从有向无环图中选择一个没有前驱的顶点-即该顶点入度为0的顶点-输出；

2.从图中删除该顶点和所有以它为起点的有向边；

.重复1，2直到该有向无环图为空或当前不存在无前驱的顶点为止，后者情况说明该有向图存在环，拓扑排序失败。

bool TopoSort(Graph G){

​ InitStatck(S); //使用存放入度为0的顶点，也可使用队列，不一定要使用栈；

​ V v = find_indegree_equ_zero(G);

​ Push(S,v);

​ while(!IsEmpty(S)){ //O(VE) ,V为遍历的顶点，E为每个顶点所需删除的边即需修改下一顶点的入度次数

​ Pop(S,temp_v);

​ print(temp_v)；count; //输出该结点并计数；

​ reduce_nextv_indegree(temp_v,1);//下一节点

​ V v = find_indegree_equ_zero(G);

​ Push(S,v);

​ }

​ if(count < sum(G.V)) return false; //拓扑排序失败，图中存在回路；

​ else return true;//拓扑排序成功，该图为AOV网；

}

算法时间复杂度度为O(VE);

工程问题中：

1）入度为0的顶点为，这个工程开始活动或继续活动，即该活动没有前驱活动或该活动的前驱活动已完成；

2）若活动线性有向排列，则拓扑排序唯一；例 1->2->，拓扑排序12 注：活动线性有向排列 是 拓扑排序唯一 的充分不必要条件；

）若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为三角矩阵；（按照拓扑排序的结果重新安排顶点的序号，生成的新的邻接矩阵为三角矩阵；）

一般的图，其邻接矩阵为三角矩阵**（充分不必要条件）**，则存在拓扑排序；反之不然；

求解AOE网问题，带权有向图，顶点表示事件，边表示活动；

解决问题：

1）完成整个项目工程至少需要多少时间（关键路径）？

2）为缩短完成工程的时间，应加快哪些活动(AOE中的边)? 或者说哪些活动是影响工程的关键？

完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的花费之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。

关键路径上的花费即完成该工程项目至少需要的时间，即整个项目的完成时间(时间最长)，即最早完成时间（书上说法）；

1.事件的最早发生时间(到达该事件至少需要多少时间，即到达该事件最久时间)

V源=0；

Ve(k)=Max{Ve(j)w(Vj,Vk)} 注:计算Ve(k)按从前往后顺序计算

2.事件的最迟发生时间(最迟发生与下一事件活动时间为下一事件的最早发生时间)

Vl(汇点)=Ve(汇点);

Vl(j)=Min{Vl(k)-w(Vj,Vk)} 注：计算Vl(j)按从后往前顺序计算

.活动的最早开始时间

活动的起点表示的事件的最早发生时间e(i)=Ve(k);

4.活动的最迟开始时间

活动终点所表示的事件的最迟发生时间与该活动之差l(i)=Vl(j)-w(Vk,Vj),<Vk,Vj>表示活动ai;

5.活动完成的时间余量

d(i)=l(i)-e(i); 若一个活动的时间余量为0，则说明该活动ai为关键活动，不如期完成会影响整个工程的进度；

注：

1）构造关键路径需要拓扑排序

2）关键活动的最早开始时间与最晚开始时间相等

具体实例：

[外链图片转存失败(img-v1S9xpY-156872822125)(F:\Tim\1094201572\MobileFile\关键路径.jpg)]

关键路径（v1,v,v4,v6) 关键路径上的活动有a2，a5,a7