`

【算法导论】最小生成树扩展

 
阅读更多

一,次最小生成树

定义:设T是图G的最小生成树,如果T1满足ω(T1)=min{ω(T’)| T’∈Not(T)},则T1是G的次小生成树。

解释:除了最小生成树外,另外一个生成树的权值和最小的生成树,定义为次最小生成树。

经典题目:POJ1679 The Unique MST,对于一张图,判断最小生成树是否惟一。惟一的定义是:不存在第二棵生成树,它的权值与最小生成树的权值相等。w(次最小生成树)!=w(最小生成树)

算法的思路:1,先生成一棵最小生成树,

2,然后枚举生成树以外的边,每次添加了一条边后,会产生一个环

3,依次去掉环上的除新添加的边以外的权值最大边,然后判断新的生成树与原生成树权值是否相同(不可能比原来生成树的权值要小)

总体思路:简单地说就是判断新添加的边是否与环上原有的边权值最大的边具有相同的权值。(原因:最小生成树选取的边都是权值最小的,剩余的边>=最小生成树最大的边)

方法一:先求最小生成树,标记出构成最小生成树边,然后枚举这些边,每次删一条,然后求一次生成树,将其值保存起来。求完之后,把删除的边补回去。进行下一次删边,枚举过程中保存最小值,如果最小值跟原来的最小生成树的值相等的话,则说明,该最小生成不唯一,反之唯一。

方法二:用Prim算法求一棵最小生成树,利用Prim算法的特性,即对于每一步扩展,都保持扩展的结果是一棵树,为了方便下一步枚举边的判断,我们用一个Max数组记录最小生成树上任意两点之间的最大边权(这里存在歧义,正解为:找到i点跟j点之间所有边中最大的一条边),这一步在Prim算法中很容易做到,因为Max[i][j]=max{Max[i][k],edge[k][j]}。接下来的操作就是枚举每一条不在最小生成树中的边,对于edge[i][j],判断它是否等于Max[i][j],若相等,则说明最小生成树不惟一。

PS:需要改进的地方,我在边与点之间做了一些映射,空间开销比较大,编程复杂度也高,以后想办法写得更简洁一些。(update:对于数据量小的题,用邻接矩阵存比较方便 )

二,度限制最小生成树

定义:一个最小生成树,有一个节点p的度数限制为=k

求解:1,将p周围所有边删掉,然后在每一个连通子图里,求最小生成树

2,将所有连通子图,选任意一条边连接到p上。此时构成一棵树,如果此时p的度数正好等于其限制的度数,则该数就是答案。如果大于限制,则无解。如果小于限制则进行步骤3。

3,为了使p的度数=k,设现在的最小生成树为T。枚举每一条(p,i)!∈T,找到T中P到i经过边最的权值(不是与P直接相连的)记为Maxi。删掉权值为Maxi的那条边,增加(P,i)且P度数增加1。

4,此时P度数依然小于限制,执行步骤3。

例题:POJ 1639 Picnic Planning(限于目前水平……)

三,最优比率生成树

定义:对于每一条边存在两个权值,分别是花费和长度,要生成一个树,使得总的花费比上总的长度最小。

例题:poj 2728 desert king(限于目前水平……)

分享到:
评论

相关推荐

    最小生成树Prim算法

    最小生成树是图论中的一个重要概念,用于寻找一个无向加权图的边集合,这些边连接了图中的所有顶点,且总权重尽可能小。Prim算法是解决这一问题的有效方法之一,由捷克数学家Vojtěch Jarník在1930年提出,后由...

    算法导论试题及答案

    3. **图算法**:Dijkstra算法、Floyd-Warshall算法、Prim算法和Kruskal算法等,用于解决最短路径问题和最小生成树问题。 4. **动态规划**:了解基本的动态规划思想,如背包问题、最长公共子序列、矩阵链乘法等问题...

    算法导论习题解答 算法导论习题解答

    例如,可能会有对冒泡排序、快速排序、二分查找、Dijkstra最短路径算法、Kruskal最小生成树算法、Floyd-Warshall所有对最短路径算法等经典算法的详细解释和实例代码。 通过解读书中的习题,学习者不仅可以提升解决...

    算法导论(第2版)_(美)Cormen_中文版

    2. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL树和红黑树)、图(图的遍历、最小生成树、最短路径等)。 3. **递归与分治**:递归的基本概念、斐波那契数列、快速排序、归并排序、汉诺塔问题、...

    算法导论中文版

    3. **图算法**:如Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法、Prim最小生成树算法和Kruskal最小生成树算法,这些都是解决网络优化问题的重要工具。 4. **动态规划**:介绍了背包问题、最长公共子...

    算法导论第三版 教师用书

    不相交集合的数据结构是用于跟踪和管理一组元素的分割,特别是在图论中的应用,如求解最小生成树、最短路径等问题。 图算法部分介绍了图的相关概念和算法,包括遍历、搜索、最短路径、最小生成树等。最小生成树是...

    算法导论第二十三章习题解答

    《算法导论》第二十三章主要探讨的是图算法,包括图的基本概念、图的表示方法、图的遍历以及各种图的特殊结构如最小生成树、最短路径等。本章习题解答涵盖了这些核心知识点,旨在帮助读者深入理解和应用所学理论。 ...

    算法导论第十四章习题解答

    第十四章通常聚焦于图算法,这包括了网络流、最小生成树、最短路径等核心概念。在解读书中的习题时,我们不仅可以深化对这些算法的理解,还能提升编程能力。 一、网络流问题 网络流问题在实际应用中广泛出现,如...

    算法导论习题解答 4-1

    2. **最小生成树**:Prim算法和Kruskal算法是构建图的最小生成树的经典算法。Prim算法从一个顶点开始,逐步扩展到其他顶点,每次选择连接两个集合的边中权值最小的一条。而Kruskal算法则是按边的权值从小到大排序,...

    MIT算法导论中文版

    3. **图算法**:如Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法、Prim最小生成树算法、Kruskal最小生成树算法等。这些算法在路由规划、网络设计等领域有着广泛应用。 4. **动态规划**:动态规划是一种...

    山东大学计算机2018年算法导论试题.

    最小生成树问题是为了在加权无向图中找到连接所有顶点的边权重最小的树。试题中提到了两种经典的算法:Kruskal's Algorithm和Prim's Algorithm。Kruskal算法通过按边的权重排序,依次选择未形成环的最小边;而Prim算...

    算法导论第三版(高清带目录书签无解压密码)

    《算法导论》是计算机科学领域的一本经典著作,它由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同撰写,全面而深入地介绍了各种基本算法及其分析。第三版在前两版的基础上...

    2020深圳大学《算法导论》期中考试试卷(含答案).pdf

    - **最小生成树**:Prim算法和Kruskal算法分别采用贪心策略构建最小生成树。 #### 5. 动态规划 - **基本概念**:动态规划是一种将问题分解为更小的子问题来解决的方法,通过保存中间结果避免重复计算。 - **经典...

    算法导论.zip

    3. **图算法**:图算法是算法中的一大分支,包括深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径算法(如Dijkstra算法和Floyd-Warshall算法)、最小生成树(Prim和Kruskal算法)等。这些算法在网络路由、社交...

    算法导论电子书

    6. **贪心算法**:介绍了贪心策略,如霍夫曼编码、Prim最小生成树算法、Kruskal最小生成树算法等。 7. **图算法**:涵盖了图的遍历(深度优先搜索、广度优先搜索)、最短路径算法(Dijkstra算法、Floyd-Warshall...

    算法导论第二版中文及答案.zip

    5. **图论与网络流**:图论是算法分析中的一个重要分支,涵盖了最短路径算法(如Dijkstra算法和Floyd-Warshall算法)、最小生成树(Prim算法和Kruskal算法)等。网络流问题涉及最大流量和最小割等概念,这些在通信...

    麻省算法导论全集(教材+讲义+答案)

    教材中的实例丰富,涵盖了从基础的冒泡排序到复杂的最小生成树问题,旨在培养读者的逻辑思维能力和问题解决能力。 接着,"讲义"部分通常是教师授课时的笔记,可能包含课堂讲解的重点、难点解析,以及额外的扩展阅读...

    算法导论答案完全版(中英文)

    - **贪心算法**:如霍夫曼编码、Prim最小生成树算法,每次选择当前最优决策以期望达到全局最优。 - **回溯法**:用于求解约束满足问题,如八皇后问题、N皇后问题。 - **分支限界法**:在搜索空间中剪枝以优化搜索...

    算法导论第三版练习答案

    在图算法部分,包括了最短路径算法(如Dijkstra算法和Floyd-Warshall算法)、拓扑排序以及最小生成树(如Prim和Kruskal算法)等内容;在动态规划部分,有背包问题、最长公共子序列、矩阵链乘法等经典问题的解决方案...

Global site tag (gtag.js) - Google Analytics