微商城网站建设公司设计一个网站要多久

当前位置： 首页 > news >正文

微商城网站建设公司,设计一个网站要多久,山东大禹建设集团网站,wordpress js 插件6.4图的应用 概念回顾—生成树 生成树#xff1a;所有顶点均由边连接在一起#xff0c;但不存在回路的图。 一个图可以有许多棵不同的生成树、含有n个顶点 n-1 条边的图不一定是生成树所有生成树具有以下共同特点 生成树的顶点个数与图的顶点个数相同#xff1b;生成树是图的…6.4图的应用 概念回顾—生成树 生成树所有顶点均由边连接在一起但不存在回路的图。 一个图可以有许多棵不同的生成树、含有n个顶点 n-1 条边的图不一定是生成树所有生成树具有以下共同特点 生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图去掉一条边则非连通一个有n个顶点的连通图的生成树有 n-1 条边在生成树中再加一条边必然形成回路。生成树中任意两个顶点间的路径是唯一的 6.4.1无向图的生成树 ​ 设图G(V,E)是个连通图当从图任一顶点出发遍历图G时将边集E(G)分层两个集合T(G)和B(G)。其中T(G)是遍历图时所经过的边的集合B(G)是遍历图时未经过的边的集合。显然G1(V,T)是图G的极小连通子图。即子图G1是连通图G的生成树。 6.4.2最小生成树 最小生成树给定一个无向网络在该网的所有生成树中使得各边权值之和最小的那棵生成树成为该网的最小生成树也叫最小代价生成树。 1、构造最小生成树 构造最小生成树的算法很多其中多数算法都利用了MST的性质。 MST性质设N(V,E)是一个连通网U是顶点集V的一个非空子集。若边(u,v)是一条具有最小权值的边其中u∈Uv∈V-U则必存在一棵包含边uv的最小生成树。 MST性质解释 ​ 在生成树的构造过程中图中n个顶点分属两个集合 已落在生成树上的顶点集U 尚未落在生成树上的顶点集V-U 接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
2、构造最小生成树算法 普里姆Prim算法 算法思想 设NV,E是连通网TE是N上最小生成树中边的集合。初始令U{u0}u0∈VTE{}。在所有u∈Uv∈V-U的边uv∈E中找一条代价最小的边u0v0。将u0,v0并入集合TE同时v0并入U。重复上述操作直至UV为止则TV,TE为N的最小生成树。 克鲁斯卡尔Kruskal算法 算法思想 设连通图NV,E令最小生成树初始状态只有n个顶点而无边的非连通图T(V,{})每个顶点自成一个连通分量。在E中选取代价最小的边若该边依附的顶点落在T中不同的连通分量上即不能形成环则将此边加入到T中否则舍去此边选取下一条代价最小的边。依此类推直至T中所有顶点都在同一连通分量上为止。 最小生成树可能不唯一 两种算法比较 算法名普里姆算法克鲁斯卡尔算法算法思想选择点选择边时间复杂度O(n2) (n为顶点数)O(eloge) (e为边数)适应范围稠密图稀疏图 6.4.3最短路径 典型用途交通网络的问题—从甲地到乙地之间是否有公路连通在有多条通路的情况下哪一条路最短 交通网络用有向网来表示 顶点——表示地点 弧——表示两个地点有路连通 弧上的权值——表示两地点之间的距离交通费或途中所花费的时间等。 ​ 如何能够使一个地点到另一个地点的运输时间最短或运费最省这就是一个求两个地点间的最短路径问题。 问题抽象在有向网中A点源点到达B点终点的多条路径中个寻找一条各边权值之和最小的路径即最短路径。 ​ 最短路径与最小生成树不同路径上不一定包含n个顶点也不一定包含n-1条边。 第一类问题两点间最短路径 第二类问题某源点到其他各点最短路径 两种常见的最短路径问题 单源最短路径—用Dijkstra迪杰斯特拉算法所有顶点间的最短路径—用Floyd弗洛伊德算法 1、Dijkstra算法 初始化先找出从源点v0到各终点vk的直达路径v0vk即通过一条弧到达的路径。 选择从这些路径中找出一条长度最短的路径v0u 更新然后对其余各条路径进行适当的调整 若在图中存在弧uvk且v0uuvkv0vk则以路径v0uvk代替v0vk。 在调整后的各条路径中再找长度最短的路径依此类推。
迪杰斯特拉Dijkstra算法按路径长度递增次序产生最短路径。 把V分成两组 S已求出最短路径的顶点的集合。TV-S尚未确定最短路径的顶点集合。 将T中顶点按最短路径递增的次序加入到S中。 保证1从源点v0到S中各顶点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度。 ​ 2每个顶点对应一个距离值 ​ S中顶点从v0到此顶点的最短路径长度。 ​ T中顶点从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度。
所有顶点间的最短路径 方法一每次以一个顶点为源点重复执行Dijkstra算法n次。 方法二弗洛伊德Floyd算法。 2、Floyd算法 算法思想 逐个顶点试探从vi到vj的所有可能存在的路径中选出一条长度最短的路径 例如采用Floyd算法求图中各顶点之间最短路径 求最短路径步骤 ​ 初始时设置一个n阶方阵令其对角线元素为0若存在弧vi,vj则对应元素为权值否则为∞ ​ 逐步试着在原直接路径中增加中间顶点若加入中间顶点后路径变短则修改之否则维持原值。所有顶点试探完毕算法结束。 6.4.4拓扑排序 1、有向无环图 有向无环图无环的有向图简称DAG图Directed Acycline Graph ​ 有向无环图常用来描述一个工程或系统的进行过程。通常把计划、施工、生产、程序流程等当成是一个工程 ​ 一个工程可以分为若干个子工程只要完成了这些子工程活动就可以导致整个工程的完成。 AOV网拓扑排序 ​ 用一个有向图表示一个工程的各子工程及其相互制约的关系其中以顶点表示活动弧表示活动之间的优先制约关系称这种有向图为顶点表示活动的网简称AOV网Activity Vertex network。 ​ 特点 若从 i 到 j 有一条有向路径则 i 是 j 的前驱j 是 i 的后继。若i,j是网中有向边则 i 是 j 的直接前驱j 是 i 的直接后继。AOV网中不允许有回路因为如果有回路存在则表明某项活动以自己为先决条件显然这是荒谬的。 问题如何判别AOV网中是否存在回路 AOE网关键路径 ​ 用一个有向图表示一个工程的各子工程及其相互制约的关系以弧表示活动以顶点表示活动的开始或结束事件称这种有向图为边表示活动的网简称为AOE网Activity On Edge。 拓扑排序 ​ 在AOV网没有回路的前提下我们将全部活动排列成一个线性序列使得若AOV网中有弧i,j存在则在这个序列中i 一定排在 j 的前面具有这个性质的线性序列称为拓扑有序序列相应的拓扑有序排序的算法称为拓扑排序。 拓扑排序的方法 在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶点和所有以它为尾的弧。重复上述两步直至全部顶点均已输出或者当图中不存在无前驱的顶点为止。 一个AOV网的拓扑序列不是唯一的 检测AOV网中是否存在环方法 ​ 对有向图构造其顶点的拓扑有序序列若网中所有顶点都在它的拓扑有序序列中则该AOV网必定不存在环。 关键路径 ​ 把工程计划表示为边表示活动的网络即AOE网用顶点表示事件弧表示活动弧的权表示活动持续时间。 事件表示在它之前的活动已经完成在它之后的活动可以开始。 对于AOE网我们关心两个问题 完成整项工程至少需要多少时间那些活动是影响工程进度的关键 关键路径——路径长度最长的路径。 路径长度——路径上各活动持续时间之和。 如何确定关键路径需要定义4个描述量 ve(vj)——表示事件 vj 的最早发生时间。 ​ 例如ve(v1)0 ve(v2)30 vl(vj)——表示事件 vj 的最迟发生时间。 ​ 例如vl(v4)165 e(i)——表示活动 ai 的最早开始时间。 ​ 例如e(a3)30 l(i)——表示活动 ai 的最迟开始时间。 ​ 例如l(a3)120 l(i) - e(i)——表示完成活动 ai 的时间余量。 ​ 例如l(3) - e(3)90 关键活动——关键路径上的活动即 l(i)e(i)即l(i) - e(i) 0的活动。 关键路径的讨论 若网中有几条关键路径则需加快同时在几条关键路径上的关键活动。 如a11,a10,a8,a7。 如果一个活动处于所有的关键路径上那么提高这个活动的速度就能缩短整个工程的完成时间。如a1、a4。 处于所有的关键路径上的活动完成时间不能缩短太多否则会使原来的关键路径变成不是关键路径。这时必须重新寻找关键路径。如a1由6天变成3天就会改变关键路径。