纺织品做外贸一般在哪个网站上wordpress有赞

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

纺织品做外贸一般在哪个网站上,wordpress有赞,网站建设大全,网站规划书包含哪些内容前置知识#xff1a;图的遍历 图的应用是408初试历年考查的重点。不过一般而言#xff0c;这部分内容直接以算法设计题形式考查的可能性极小#xff0c;更多的是结合图的实例来考查算法的具体操作过程#xff0c;要求掌握的是手推模拟给定图的各个算法执行过程。此外#…前置知识图的遍历 图的应用是408初试历年考查的重点。不过一般而言这部分内容直接以算法设计题形式考查的可能性极小更多的是结合图的实例来考查算法的具体操作过程要求掌握的是手推模拟给定图的各个算法执行过程。此外还需对给定模型建立相应的图去解决问题。 最小生成树 知识点回顾图的基本概念-生成树 一个连通图的生成树包含图的所有顶点并且只含尽可能少的边。对于生成树来说若砍去(减少)它的一条边则会使生成树变成非连通图若给它增加一条边则会形成图中的一条回路(环)。 对于一个带权连通无向图 G G G生成树不同每棵树的权即树中所有边上的权值之和也可能不同。权值之和最小的那棵生成树称为 G G G的最小生成树 M i n i m u m − S p a n n i n g − T r e e Minimum-Spanning-Tree Minimum−Spanning−Tree M S T MST MST。 最小生成树的性质 若图 G G G中存在权值相同的边则 G G G的最小生成树可能不唯一即最小生成树的树形可能不唯一。当图 G G G中的各边权值互不相等时 G G G的最小生成树是唯一的若无向连通图 G G G的边数比顶点数少 1 1 1即 G G G本身是一棵树时则图 G G G的最小生成树就是其本身只有连通图才有生成树非连通图只有生成森林。虽然最小生成树可能不唯一但其对应的边的权值之和总是唯一的并且是最小的。最小生成树的边数为顶点数减 1 1 1。树的性质 注意最小生成树中所有边的权值之和最小不代表任意两个顶点之间的路径是最短路径。 构造最小生成树有多种算法但大多数算法都利用了最小生成树的下列性质假设 G ( V , E ) G(V,E) G(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)的最小生成树。 基于该性质的最小生成树算法主要有 P r i m Prim Prim算法和 K r u s k a l Kruskal Kruskal算法它们都是基于贪心算法的策略即通过多个局部最优解得到全局最优解。408初试中需要掌握这两个算法的本质含义和基本思想并能够手动模拟推演出其算法的实现步骤。 王道书上给出了一个通用的最小生成树算法的伪代码 GENERIC_MST(G) {TNULL;while T 未形成一棵生成树;do 找到一条最小代价边(u,v)并加入T后不会产生回路;TT∪(u,v); }P r i m Prim Prim算法 P r i m Prim Prim普里姆算法的执行非常类似于寻找图的最短路径的 D i j k s t r a Dijkstra Dijkstra算法下一节会讲。 P r i m Prim Prim算法构造最小生成树的过程如下图 6.15 6.15 6.15所示王道考研408数据结构2025 - P241。初始时选取图中任一顶点如顶点 1 1 1加入树 T T T此时树中只含有一个顶点之后选择一个与当前 T T T中顶点集合距离最近的顶点并将该顶点和相应的边加入 T T T每次操作后 T T T中的顶点数和边数都增加 1 1 1。以此类推直至图中所有的顶点都并入 T T T得到的 T T T就是最小生成树。 图片来自王道考研408数据结构2025 P r i m Prim Prim算法的步骤如下 假设 G { V , E } G {V,E} G{V,E}是连通图其最小生成树 T ( U , E T ) T(U,E_T) T(U,ET​) E T E_T ET​是最小生成树中边的集合。初始化向空树 T ( U , E T ) T(U,E_T) T(U,ET​)中添加图 G ( V , E ) G(V,E) G(V,E)的任意一个顶点 u 0 u_0 u0​使 U { u 0 } U{u_0} U{u0​} E T ∅ E_T\emptyset ET​∅。循环重复下列操作直至 U V UV UV从图 G G G中选择满足 { ( u , v ) ∣ u ∈ U , v ∈ V − U } \left { \left ( u,v \right ) \mid u \in U, v \in V-U \right } {(u,v)∣u∈U,v∈V−U}且具有最小权值的边 ( u , v ) (u,v) (u,v)加入树 T T T置 U U ∪ { v } U U \cup \left { v \right } UU∪{v} E T E T ∪ { ( u , v ) } E_T E_T \cup \left { \left ( u,v \right ) \right } ET​ET​∪{(u,v)}。 王道书上给出的 P r i m Prim Prim算法简单实现的伪代码如下感兴趣的读者可以尝试完善之 void Prim(G, T){T∅; //初始化空树U{w}; //添加任意一个顶点wwhile((V-U)!∅){ //若树中不含全部顶点设(u,v)是使u∈U与v∈(V−U)且权值最小的边TT∪{(u,v)}; //边归入树UU∪{v}; //顶点归入树} }P r i m Prim Prim算法的时间复杂度为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)不依赖于 ∣ E ∣ |E| ∣E∣因此它适用于求解稠密图的最小生成树。虽然采用其他方法能改进 P r i m Prim Prim算法的时间复杂度但增加了实现的复杂性。 相关例题PTA 7-50 畅通工程之局部最小花费问题传送门 K r u s k a l Kruskal Kruskal算法 与 P r i m Prim Prim算法从顶点开始扩展最小生成树不同 K r u s k a l Kruskal Kruskal克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。 K r u s k a l Kruskal Kruskal算法构造最小生成树的过程如下图 6.16 6.16 6.16所示王道考研408数据结构2025 - P241。初始时为只有 n n n个顶点而无边的非连通图 T { V , { } } T \left { V,\left { \right } \right } T{V,{}}每个顶点自成一个连通分量。然后按照边的权值由小到大的排序不断选取当前未被选取过且权值最小的边若该边依附的顶点落在 T T T中不同的连通分量上使用并查集判断这两个顶点是否属于同一棵集合树则将此边加入 T T T否则舍弃此边而选择下一条权值最小的边。以此类推直至 T T T中所有顶点都在一个连通分量上。 图片来自王道考研408数据结构2025 知识点回顾并查集 K r u s k a l Kruskal Kruskal算法的步骤如下 假设 G { V , E } G {V,E} G{V,E}是连通图其最小生成树 T ( U , E T ) T(U,E_T) T(U,ET​)。初始化 U V UV UV E T ∅ E_T\emptyset ET​∅。即每个顶点构成的一棵独立的树 T T T此时是一个仅含 ∣ V ∣ |V| ∣V∣个顶点的森林。循环重复直至 T T T是一棵树按 G G G的边的权值递增顺序依次从 E − E T E-E_T E−ET​中选择一条边若这条边加入 T T T后不构成回路则将其加入 E T E_T ET​否则舍弃直到 E T E_T ET​中含有 n − 1 n-1 n−1条边。 王道书上给出的 K r u s k a l Kruskal Kruskal算法简单实现的伪代码如下感兴趣的读者可以尝试完善之 void Kruskal(V,T){TV; //初始化树T仅含顶点numSn; //连通分量数while(numS1){ //若连通分量数大于1从E中取出权值最小的边(v,u);if(v和u属于T中不同的连通分量){TT∪{(v,u)}; //将此边加入生成树中numS–; //连通分量数减1}} }根据图的相关性质若一条边连接了两棵不同树中的顶点则对这两棵树来说它必定是连通的将这条边加入森林中完成两棵树的合并直到整个森林合并成一棵树。 在 K r u s k a l Kruskal Kruskal算法中最坏情况下需要对 ∣ E ∣ |E| ∣E∣条边各扫描一次。通常采用堆第 7 7 7章里会讲来存放边的集合每次选择最小权值的边需要 O ( l o g 2 ∣ E ∣ ) O(log_2|E|) O(log2​∣E∣)的时间每次使用并查集来快速判断两个顶点是否属于一个集合所需的时间为 O ( α ( ∣ V ∣ ) ) O(α(|V|)) O(α(∣V∣)) α ( ∣ V ∣ ) α(|V|) α(∣V∣)的增长极其缓慢可视为常数。算法的总时间复杂度为 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣)不依赖于 ∣ V ∣ |V| ∣V∣因此 K r u s k a l Kruskal Kruskal算法适合顶点较多的稀疏图。 相关例题洛谷P3366 【模板】最小生成树传送门 个人题解【洛谷P3366】【模板】最小生成树 解题报告 对本小节内容需要掌握手推Prim算法和Kruskal算法过程能够模拟构建最小生成树如有余力可以打一些代码题增强理解。 以上。