重庆璧山网站制作公司电话,c 网站开发 调试,asp网站后台上传不了图片,在本地搭建多个网站6.4 图的应用
6.4.1 最小生成树
对于⼀个带权连通⽆向图G (V, E)#xff0c;⽣成树不同#xff0c;每棵树的权#xff08;即树中所有边上的权值之和#xff09;也可能不同。设R为G的所有⽣成树的集合#xff0c;若T为R中边的权值之和最小的生成树#xff0c;则T称为G的…6.4 图的应用
6.4.1 最小生成树
对于⼀个带权连通⽆向图G (V, E)⽣成树不同每棵树的权即树中所有边上的权值之和也可能不同。设R为G的所有⽣成树的集合若T为R中边的权值之和最小的生成树则T称为G的最小生成树Minimum-Spanning-Tree, MST。 最小生成树可能有多个但边的权值之和总是唯一且最小的 最小生成树的边数顶点数–1。砍掉一条则不连通增加一条边则会出现回路
求最小生成树 Prim算法(普里姆): 从某一个顶点开始构建生成树; 每次将代价最小的新顶点纳入生成树 直到所有顶点都纳入为止。
Kruskal算法(克鲁斯卡尔): 每次选择一条权值最小的边使这条边的两头连通原本已经连通的就不选) 直到所有结点都连通Prim算法的实现思想 第1轮:循环遍历所有个结点找到lowCost最低的且还没加入树的顶点 第2轮︰循环遍历所有个结点找到lowCost最低的且还没加入树的顶点 第3轮:循环遍历所有个结点找到lowCost最低的且还没加入树的顶点 第4轮:循环遍历所有个结点找到lowCost最低的且还没加入树的顶点 第5轮循环遍历所有个结点找 到lowCost最低的且还没加入树的顶点Kruskal 算法的实现思想 第1轮检查第1条边的两个顶点是否 连通是否属于同⼀个集合 第2轮检查第2条边的两个顶点是否 连通是否属于同⼀个集合 第3轮检查第3条边的两个顶点是否 连通是否属于同⼀个集合 第4轮检查第4条边的两个顶点是否 连通是否属于同⼀个集合 第5轮检查第5条边的两个顶点是否 连通是否属于同⼀个集合 第6轮检查第6条边的两个顶点是否 连通是否属于同⼀个集合
6.4.2_1 最短路径问题_BFS算法
BFS求无权图的单源最短路径
#define MAX_LENGTH 2147483647 //地图中最大距离表示正无穷//求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){//d[i]表示从u到i结点的最短路径for(i0; iG.vexnum; i){visited[i]FALSE; //初始化访问标记数组d[i]MAX_LENGTH; //初始化路径长度path[i]-1; //初始化最短路径记录}InitQueue(Q); //初始化辅助队列d[u]0;visites[u]TREE;EnQueue(Q,u);while(!isEmpty[Q]){ //BFS算法主过程DeQueue(Q,u); //队头元素出队并赋给ufor(wFirstNeighbor(G,u);w0;wNextNeighbor(G,u,w)){if(!visited[w]){ //w为u的尚未访问的邻接顶点d[w]d[u]1; //路径长度1path[w]u; //最短路径应从u到wvisited[w]TREE; //设已访问标记EnQueue(Q,w); //顶点w入队}}}
}6.4.2_2 最短路径问题_Dijkstra算法
使用 Dijkstra算法求最短路径问题需要使用三个数组 final[]数组用于标记各顶点是否已找到最短路径。 dist[]数组用于记录各顶点到源顶点的最短路径长度。 path[]数组用于记录各顶点现在最短路径上的前驱。
算法思想循环遍历所有结点找到还没确定最短路径、且dist最小的顶点Vi令final[i]ture。 检查所有邻接自Vi的顶点若其final值为false,则更新dist和path信息。
#define MAX_LENGTH 2147483647;// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){for(int i0; iG.vexnum; i){ //初始化数组final[i]FALSE;dist[i]G.edge[u][i];if(G.edge[u][i]MAX_LENGTH || G.edge[u][i] 0)path[i]-1;elsepath[i]u;final[u]TREE;}for(int i0; iG.vexnum; i){int MINMAX_LENGTH;int v;// 循环遍历所有结点找到还没确定最短路径且dist最⼩的顶点vfor(int j0; jG.vexnum; j){if(final[j]!TREE dist[j]MIN){MIN dist[j];v j;}}final[v]TREE;// 检查所有邻接⾃v的顶点路径长度是否最短for(int j0; jG.vexnum; j){if(final[j]!TREE dist[j]dist[v]G.edge[v][j]){dist[j] dist[v]G.edge[v][j];path[j] v;}}}
}Dijkstra算法能够很好的处理带权图的单源最短路径问题但不适⽤于有负权值的带权图。
6.4.2_3 最短路径问题_Floyd算法
Floyd算法求出每⼀对顶点之间的最短路径使⽤动态规划思想将问题的求解分为多个阶段。
Floyd算法使用到两个矩阵 dist[]目前各顶点间的最短路径。 path[]两个顶点之间的中转点。
//...准备工作根据图的信息初始化矩阵A和pathfor(k0;kn;k){ //考虑以Vk作为中转点for(i0;in;i){ //遍历整个矩阵i为行号j为列号for(j0;jn;j){if(A[i][j]A[i][k]A[k][j]){ //以Vk为中转地按的路径更短A[i][j]A[i][k]A[k][j]; //更新最短路径长度path[i][j]k; //中转点}}}}Floyd算法不能解决带有“负权回路”的图(有负权值的边组成回路)这种图有可能没有最短路径
最短路径算法比较
BFS算法Dijkstra算法 Floyd算法无权图✔✔✔带权图✘✔✔带负权值的图✘✘✔带负权回路的图✘✘✘时间复杂度O(|V|^2)或O(|V||E|)O(|V|^2)O(|V|^3)通常用于求无权图的单源最短路径 求带权图的单源最短路径求带权图中各顶点间的最短路径
6.4.3 有向无环图描述表达式
有向无环图:若一个有向图中不存在环则称为有向无环图简称DAG图(Directed Acyclic Graph) 解题方法 练习
6.4.4 拓扑排序
AOV网(Activity on vertex Network用顶点表示活动的网): 用DAG图(有向无环图表示一个工程。顶点表示活动有向边Vi,Vj表示活动Vi必须先于活动Vj进行
拓扑排序︰在图论中由一个有向无环图的顶点组成的序列当且仅当满足下列条件时称为该图的一个拓扑排序: ①每个顶点出现且只出现一次。 ②若顶点A在序列中排在顶点B的前面则在图中不存在从顶点B到顶点A的路径。
或定义为:拓扑排序是对有向无环图的顶点的一种排序它使得若存在一条从顶点A到顶点B的路径则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。
拓扑排序的实现 ① 从AOV网中选择⼀个没有前驱入度为0的顶点并输出。 ② 从网中删除该顶点和所有以它为起点的有向边。 ③ 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止 代码实现拓扑排序
#define MaxVertexNum 100 //图中顶点数目最大值typedef struct ArcNode{ //边表结点int adjvex; //该弧所指向的顶点位置struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;typedef struct VNode{ //顶点表结点VertexType data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];typedef struct{AdjList vertices; //邻接表int vexnum,arcnum; //图的顶点数和弧数
}Graph; //Graph是以邻接表存储的图类型// 对图G进行拓扑排序
bool TopologicalSort(Graph G){InitStack(S); //初始化栈存储入度为0的顶点for(int i0;ig.vexnum;i){if(indegree[i]0)Push(S,i); //将所有入度为0的顶点进栈}int count0; //计数记录当前已经输出的顶点数while(!IsEmpty(S)){ //栈不空则存入Pop(S,i); //栈顶元素出栈print[count]i; //输出顶点ifor(pG.vertices[i].firstarc;p;pp-nextarc){//将所有i指向的顶点的入度减1并将入度为0的顶点压入栈vp-adjvex;if(!(--indegree[v]))Push(S,v); //入度为0则入栈}}if(countG.vexnum)return false; //排序失败,有向图中有回路elsereturn true; //拓扑排序成功
}拓扑排序 每个顶点都需要处理一次 每条边都需要处理一次 时间复杂度O(|V||E|) 若采用邻接矩阵则需O(|V^2|)
逆拓扑排序 对一个AOV网如果采用下列步骤进行排序则称之为逆拓扑排序: ①从AOV网中选择一个没有后继出度为O)的顶点并输出。 ②从网中删除该顶点和所有以它为终点的有向边。 ③重复①和②直到当前的AOV网为空。
逆拓扑排序的实现(DFS算法)
void DFSTraverse(Graph G){ //对图G进行深度优先遍历for(v0; vG.vexnum;V)visited[v]FALSE; //初始化已访问标记数据for(v;vG.vexnum; V) //本代码中是从v0开始遍历if(!visited[v])DFS(G,v);
}void DFS(Graph G,int v){ //从顶点v出发深度优先遍历图Gvisited [v]TRUE; //设已访问标记for(wFirstNeighbor(G,v);w0 ; wNextNeighor(G,v,w))if(!visited[w]){ //w为u的尚未访问的邻接顶点DFS(G,w);}//ifprint(v); //输出顶点
} 6.4.5 关键路径
AOE 网在带权有向图中以顶点表示事件以有向边表示活动以边上的权值表示完成该活动的开销如完成活动所需的时间称之为用边表示活动的网络简称 AOE 网 (Activity On Edge NetWork)。
AOE网具有以下两个性质 ①只有在某顶点所代表的事件发⽣后从该顶点出发的各有向边所代表的活动才能开始 ②只有在进⼊某顶点的各有向边所代表的活动都已结束时该顶点所代表的事件才能发⽣。 在 AOE 网中仅有⼀个入度为 0 的顶点称为开始顶点源点它表示整个⼯程的开始 也仅有⼀个出度为 0 的顶点称为结束顶点汇点它表示整个⼯程的结束。
在AOE网中有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条所有路径中具有最大路径长度的路径称为关键路径而把关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度若关键活动不能按时完成则整个工程的完成时间就会延长。
寻找冠军活动时所用到的几个参量的定义
1. 事件 vk的最早发生时间 ve(k)决定了所有从vk 开始的活动能够开工的最早时间。 2. 事件 vk的最迟发⽣时间 vl(k)它是指在不推迟整个工程完成的前提下该事件最迟必须发⽣的时间。 3.活动ai的最早开始时间e(i)指该活动弧的起点所表示的事件的最早发生时间。 4.活动ai的最迟开始时间l(i)它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。 5.活动 ai的时间余量d(i)l(i)−e(i)表示在不增加完成整个⼯程所需总时间的情况下活动ai可以拖延的时间若⼀个活动的时间余量为零则说明该活动必须要如期完成d(i)0 即l(i)e(i) 的活动ai是关键活动由关键活动组成的路径就是关键路径。
求关键路径的步骤 1.求所有事件的最早发生时间ve():按拓扑排序序列依次求各个顶点的ve(k) ve(源点)0 ve(k) Max{vef)W eight(vj , vk )}vj为vk的任意前驱。 2.求所有事件的最迟发生时间vl():按逆拓扑排序序列依次求各个顶点的 vl(k)vl(汇点) ve(汇点)vl(k)Min{vl(j)- W eight(vk , vi)}v为Vv\k 的任意后继。 3.求所有活动的最早发生时间e():若边Vk ,Vj表示活动a;则有e(i)ve(k)。 4.求所有活动的最迟发生时间1():若边Vk,Vj 表示活动a则有l(i) vl(j)- Weight(vi , vj)。 5.求所有活动的时间余量d(): d(i) l(i)-e(i)。
关键活动、关键路径的特性: 1.若关键活动耗时增加则整个工程的工期将增长。 2.缩短关键活动的时间可以缩短整个工程的工期。 3.当缩短到一定程度时关键活动可能会变成非关键活动。 4.可能有多条关键路径只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
