最小生成树 订阅
一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。 [1]  最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。 展开全文
一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。 [1]  最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。
信息
外文名
Minimum Spanning Tree,MST
提出者
Kruskal(克鲁斯卡尔)Prim(普里姆)
应用学科
计算机,数学(图论),数据结构
中文名
最小生成树
适用领域范围
应用图论知识的实际问题
算    法
Kruskal算法,Prim算法
最小生成树概述
在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即)且为无循环图,使得的 w(T) 最小,则此 T 为 G 的最小生成树。 最小生成树其实是最小权重生成树的简称。 [1] 
收起全文
精华内容
下载资源
问答
  • 最小生成树最小生成树最小生成树最小生成树最小生成树
  • 最小生成树

    千次阅读 2018-08-13 10:41:11
    最小生成树

    最小生成树

    首先, 什么是最小生成树
    图论基础

    Prim算法(普利姆算法)

    采用prim算法解决生成树问题

    1. 假设G=(V,E)是一个具有n个顶点的连通网,T=(U,TE)是G的最小生成树,U,TE初值均为空集。
    2. 首先从V中任取一个顶点(假定取v1),将它并入U中,此时U={v1},然后只要U是V的真子集(U∈V),就从那些一个端点已在T中,另一个端点仍在T外的所有边中,找一条最短边,设为(vi ,vj ),其中vi ∈U, vj ∈V-U,并把该边(vi , vj )和顶点vj 分别并入T的边集TE和顶点集U,如此进行下去,每次往生成树里并入一个顶点和一条边,直到n-1次后得到最小生成树。
    关键问题

    每次如何从连接T 中和T 外顶点的所有边中,找到一条最短的

    1. 如果用邻接矩阵存放图,而且选取最短边的时候遍历所有点进行选取,则总时间复杂度为O(V 2 ), V 为顶点个数
    2. 用邻接表存放图,并使用堆来选取最短边,则总时间复杂度为O(ElogV)

    特点 : 不加堆的Prim 算法适用于密集图,加堆的适用于稀疏图

    Krustral算法(克鲁斯卡尔算法)

    1. 假设G=(V,E)是一个具有n个顶点的连通网,T=(U,TE)是G的最小生成树,U=V, TE初值为空。
    2. 将图G中的边按权值从小到大依次选取,若选取的边使生成树不形成回路,则把它并入TE中,若形成回路则将其舍弃,直到TE中包含N-1条边为止,此时T为最小生成树。

    特点: 适用于稀疏图

    关键问题
    • 如何判断欲加入的一条边是否与生成树中边构成回路。
      1. 将各顶点划分为所属集合的方法来解决,每个集合的表示一个无回路的子集。开始时边集为空,N个顶点分属N个集合,每个集合只有一个顶点,表示顶点之间互不连通。
      2. 当从边集中按顺序选取一条边时,若它的两个端点分属于不同的集合,则表明此边连通了两个不同的部分,因每个部分连通无回路,故连通后仍不会产生回路,此边保留,同时把相应两个集合合并

    经典最小生成树题目畅通工程
    prim算法和kruskal算法比较

    1. Kruskal:
      • 将所有边从小到大加入,在此过程中判断是否构成回路
      • 使用数据结构:并查集
      • 时间复杂度:O(ElogE)
      • 适用于稀疏图
    2. Prim:
      • 从任一节点出发,不断扩展
      • 使用数据结构:堆
      • 时间复杂度:O(ElogV) 或 O(VlogV+E)(斐波那契堆)
      • 适用于密集图
      • 若不用堆则时间复杂度为O(V2 )

    最小生成树一·Prim算法
    生成树二·Kruscal算法

    最小生成树扩展

    最小度数限制生成树

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,036
精华内容 15,214
关键字:

最小生成树