开一个网站的流程,深圳坪山网站建设公司,关键词优化外包服务,工厂软件管理系统目录
一.最小生成树
1.生成树
2.无向图的生成树
3.最小生成树算法
二.最短路径
1.单源最短路径---Dijkstra#xff08;迪杰斯特拉#xff09;算法
2.所有顶点间的最短路径---Floyd#xff08;弗洛伊德#xff09;算法
三.有向无环图的应用
1.AOV网#xff08;拓扑…目录
一.最小生成树
1.生成树
2.无向图的生成树
3.最小生成树算法
二.最短路径
1.单源最短路径---Dijkstra迪杰斯特拉算法
2.所有顶点间的最短路径---Floyd弗洛伊德算法
三.有向无环图的应用
1.AOV网拓扑排序
2.AOE网关键路径 一.最小生成树
1.生成树
所有顶点均有边连接在一起但不存在回路的图 •一个图可以有许多棵不同的生成树 •所有生成树都具有以下共同特点 •生成树的顶点个数与图的顶点个数相同 •生成树是图的极小连通子图去掉一条边则非连通 •一个有n个顶点的连通图的生成树有(n-1)条边 •在生成树中再加一条边必然形成回路 •生成树中任意两个顶点间的路径是唯一的 •含n个顶点n-1条边的图不一定是生成树 2.无向图的生成树
无向图的生成树可以与深度优先搜索遍历与广度优先搜索遍历的方法结合起来
不了解的可以看看这篇
深度优先搜索遍历与广度优先搜索遍历
深度优先生成树V1-V2-V4-V8-V5-V3-V6-V7 广度优先生成树V1-V2-V3-V4-V5-V6-V7-V8
3.最小生成树算法
给定一个无向网络在该网所有的生成树中使得各边权值之和最小的那棵生成树称为最小生成树也叫最小代价生成树
生成最小生成树的方法
MST(Minimum Spanning Tree)
•已落在生成树上的顶点集U
•尚未落在生成树的顶点集V-U •选取权值最小的边因为权值最小的边一定存在生成树是包含他的
1普里姆Prim算法
•设N(V,E)是连通网TE是N上最小生成树中边的集合 •初始令 U{u0},(u0V) TE{}
•在所有 uU, v V-U的边(u v)E中找条代价最小的边(u0v0)
•将(u0,v0)并入集合 TE同时v0并入 U 2克鲁斯卡尔Kruskal算法
•设连通网 N(VE)令最小生成树初始状态为只有 n个顶点而无边的非连通图T(V{})每个顶点自成一个连通分量。
•在E中选取代价最小的边若该边依附的顶点落在T中不同的连通分量上(即:不能形成环则将此边加入到 T中;否则舍去此边选取下一条代价最小的边。 •依此类推直至T中所有顶点都在同一连通分量上为止。 3两种算法的区别
•普里姆算法是选择点从U集合到V-U集合找一条权值最小的边将这个边连接的点加入到U集合中而克鲁斯卡尔算法则是在所有边中找权值最小的边加入到生成树中直到所有的点连通边为n-1条。
•普里姆算法的时间复杂度为O(),对于所有的点都需要遍历其他顶点进行判断下一个加入生成树的点克鲁斯卡尔算法则是选择边和顶点数无关只跟边数有关对顶点的权值进行排序时平均情况是(eloge)
•克鲁斯卡尔算法时间复杂度只跟边数有关所以边数较少时算法时间较少所以克鲁斯卡尔算法适用于稀疏图普里姆算法适用于稠密图。 二.最短路径
在有向网中A点源点到达B点终点的多条路径中寻找一条各边权值之和最小的路径即最短路径 最短路径与最小生成树不同路径上不一定包含n个顶点也不一定包含n-1条边 •两点间的最短路径
下图最短路径值为14 •某源点到其他各点最短路径 1.单源最短路径---Dijkstra迪杰斯特拉算法
算法步骤
•初始时令S{v0},T{其余顶点}
•T中顶点对应的距离值用辅助数组D存放 •D[i]初值若v0,存在则为权值否则为
•从T中选取一个其距离值最小的顶点,加入S
•对T中顶点的距离值进行修改若加进作中间顶点从v0到的距离值比不加的路径要短则修改此距离值。
•重复上述步骤直到SV为止 以下图为例 Dijkstra迪杰斯特拉算法可以计算1个顶点到其他顶点的最短路径时间复杂度为O() 如果要计算所有顶点间的最短路径即O()*nO() 2.所有顶点间的最短路径---Floyd弗洛伊德算法
算法步骤
•逐个顶点试探
•从vi到vj的所有可能存在的路径中
•选出一条长度最短的路径 初始设置一个n阶方阵令其对角线元素为0,若存在弧vi,vj,则对应元素为权值否则为 如图A--B的权值为4,B--A的权值为6以此类推可得n阶方阵 加入A顶点如图本来C---B没有路径但是可以从C--A---B,路径长度为7 加入B如图原来A---C为11现在加入B变为A---B---C,变得更小了所以6替换11 加入C如图B---A路径长度为6B---C---A路径长度变短所以5替换6 以上总结为逐步试着在原直接路径中增加中间顶点若加入中间顶点后路径变短则修改之;否则维持原值。所有顶点试探完毕算法结束。 三.有向无环图的应用
1.AOV网拓扑排序
用一个有向图表示一个工程的各子工程及其相互制约的关系其中以顶点表示活动弧表示活动之间的优先制约关系称这种有向图为顶点表示活动的网简称 AOV网(Activity On Vertex network)
拓扑排序
拓扑排序的方法
•在有向图中选一个没有前驱的顶点且输出之
•从图中删除该顶点和所有以它为尾的弧
•重复上述两步直至全部顶点均已输出或者当图中不存在无前驱的顶点为止
注拓扑排序的结果是不唯一的 拓扑排序可以检测AOV网中是否存在环
对有向图构造其顶点的拓扑有序序列若网中所有顶点都在它的拓扑有序序列中则该AOV 网必定不存在环若还剩余顶点没有在拓扑有序序列中就存在环 2.AOE网关键路径
用一个有向图表示一个工程的各子工程及其相互制约的关系以弧表示活动以顶点表示活动的开始或结束事件称这种有向图为边表示活动的网简称为AOE网(Activity On Edge)。
关键路径
关于关键路径可以看这篇文章
http://t.csdn.cn/uitVf
如果想要理解的再深入一些可以看
http://t.csdn.cn/JfbLs
