网站建设备案策划书,无锡哪里有建设网站,如何优化网络速度,属于什么的网页制作工具文章目录 0 图的应用1 生成树1.1 无向图的生成树1.2 最小生成树1.2.1 构造最小生成树1.2.2 Prim算法构造最小生成树1.2.3 Kruskal算法构造最小生成树1.2.4 两种算法的比较 1.3 最短路径1.3.1 两点间最短路径1.3.2 某源点到其他各点最短路径1.3.3 Dijkstra1.3.4 Floyd 1.4 拓扑排… 文章目录 0 图的应用1 生成树1.1 无向图的生成树1.2 最小生成树1.2.1 构造最小生成树1.2.2 Prim算法构造最小生成树1.2.3 Kruskal算法构造最小生成树1.2.4 两种算法的比较 1.3 最短路径1.3.1 两点间最短路径1.3.2 某源点到其他各点最短路径1.3.3 Dijkstra1.3.4 Floyd 1.4 拓扑排序1.4.1 有向无环图DAG1.4.2 AOV网 1.5 关键路径1.5.1 求解关键路径 0 图的应用 1 生成树
生成树所有顶点均由边连接在一起但不存在回路的图。 也就是两个条件顶点条件和边数条件顶点都要保持连通边数达到最少没有回路。 如右边的图随便再加一条边就有回路了。 所有生成树都具有以下的共同特点
生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图去掉一条边则非连通一个有 n n n个顶点的连通图的生成树有 n − 1 n-1 n−1条边生成树中任意两个顶点间的路径是唯一的含有 n n n个顶点 n − 1 n-1 n−1条边的图不一定是生成树如下图所示 因为生成树是连通的每个顶点都要用边相连上图是不连通的有两个连通分量。
1.1 无向图的生成树
生成树要包含所有顶点那么对图进行遍历把走过的边全部加入到图当中。 遍历则采用DFS与BFS都可以。
用DFS生成的生成树就是DFS生成树。 用BFS生成的生成树就是BFS生成树。
综上
1.2 最小生成树 最小生成树给定一无向网络在该网的所有生成树中使得各边权值之和最小的那棵生成树称为该网的最小生成树也叫最小代价生成树。 最小生成树可能是不唯一的。 1.2.1 构造最小生成树
构造最小生成树的算法很多其中多数算法都利用了MST(Minimum Spanning Tree)的性质。
MST性质 其实就是贪心算法不断去找权值最小的边。 设 N ( V , E ) N(V, E) N(V,E)以目是一个连通网 U U U是顶点集 V V V的一个非空子集。若边 ( u , v ) (u, v) (u,v)是一条具有最小权值的边其中 u ∈ U , v ∈ V − U u∈U,v∈V-U u∈U,v∈V−U则必存在一棵包含边 ( u , v ) (u,v) (u,v)的最小生成树。
举例 现在 U { v 1 } U\{v_1\} U{v1}所以 V − U { v 2 , v 3 , v 4 , v 5 , v 6 } V-U\{v_2,v_3,v_4,v_5,v_6\} V−U{v2,v3,v4,v5,v6}所以 u ∈ U , v ∈ V − U u∈U,v∈V-U u∈U,v∈V−U当中其中从 v 1 v_1 v1到 v 3 v_3 v3是最小的权值为1存在这个权值最小的边这条边一定会包含在某个最下生成树当中。
1.2.2 Prim算法构造最小生成树
算法思想
1.2.3 Kruskal算法构造最小生成树
相比Prim算法更加贪心直截了当贪心前提不成环。这次开始就把所有顶点都加入到最小生成树上面去。不过并不包括边这时边的集合都是空集没包含边彼此之间不连通。 然后直接在边集合当中选权值最小的边直接加入。 以此类推选到所有顶点都连通为止前提不能形成回路n个点n-1条边。
1.2.4 两种算法的比较 Prim是选择点加入的而Kruskal是选择边的。选择边的时候和顶点数是没关系的。
1.3 最短路径
1.3.1 两点间最短路径
从起点走向终点并非要n个节点都包括也并非要n-1条边。 直到找到路径长度最短的一条路径。 这种最短路径也称为单源的最短路径采用Dijkstra算法。
1.3.2 某源点到其他各点最短路径 所有顶点的最短路径统一使用Floyd弗洛伊德算法。
1.3.3 Dijkstra
其时间复杂度为 O ( n 3 ) O(n^3) O(n3) 按照路径长度递增次序产生最短路径启发式贪心算法。 启发式算法先找最短的后面再及时更新具体过程可以看王老师的视频。
1.3.4 Floyd
其时间复杂度为 O ( n 3 ) O(n^3) O(n3)
算法思想
逐个顶点试探从少到的所有可能存在的路径中选出一条长度最短的路径 求最短路径的步骤 初始时设置一个 n n n阶方阵令其对角线元素到自身的路径为0若存在弧 v i , v j v_i, v_j vi,vj则对应元素为权值否则为 ∞ ∞ ∞。 逐步试着在原直接路径中增加中间顶点若加入中间顶点后路径变短则修改之否则维持原值。所有顶点试探完毕算法结束。 1.4 拓扑排序
1.4.1 有向无环图DAG AOV网以顶点表示活动AOE网用弧表示活动子工程。 AOV网用来解决拓扑排序AOE网用来解决关键路径问题。
拓扑排序的一个小例子
1.4.2 AOV网 问题如何判断AOV网中是否存在回路 答 所有顶点都能加入拓扑排序的话就一定没有网。
拓扑排序。 将网变成一个线性序列的过程就是拓扑排序。 拓扑排序的步骤
首先构建好AOV网 在有向图中选一个没有前驱的顶点且输出例如C1和C9假设选了C1在有向图当中删除该顶点和所有以它为尾的弧C1发出的弧即C1与C2C4C12的弧重复上述两步直至全部顶点均已输出或者当图中不存在无前驱的顶点为止
1.5 关键路径
制定计划查找关键路径。 关键路径就是从源点到汇点路径长度权值之和最长大的路径。 按照任务需求构建有权图。 举例
对于上方AOE网我们关心两个问题
完成整项女程至少需要多少时间哪些活动是影响工程进度的关键
以上答为关键路径与路径长度。
1.5.1 求解关键路径
四个有用的量 求关键路径的步骤
