本文目录
数据结构的“最小生成树”是如何定义的
连通网的最小代价生成树简称最小生成树
生成树是一个包含n个结点的连通图G的一个子图。该子图必须包含G中的所有n个结点以及G中的n-1条边并且保持连通性。 最小生成树是G的所有可能的生成树中,n-1条边的权值总和最小的那一个(或多个)生成树。
谁能告诉我最小生成树的历史起源啊
最小生成树的 prim 和 kruskal 算法faq-it.org/linux_kernel/ 克鲁斯卡尔算法 假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。 普里姆算法 假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,TV 是 WN 上最小生成树中顶点的集合,TE 是最小生成树中边的集合。显然,在算法执行结束时,TV=V,而 TE 是 E 的一个子集。在算法开始执行时,TE 为空集,TV 中只有一个顶点,因此,按普里姆算法构造最小生成树的过程为:在所有“其一个顶点已经落在生成树上,而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边,逐条加在生成树上,直至生成树中含有 n-1条边为止。***隐藏网址***抱歉,实在找不到它的历史
最小生成树的两种算法
主要有两个:1.普里姆(Prim)算法 特点:时间复杂度为O(n2).适合于求边稠密的最小生成树。2.克鲁斯卡尔(Kruskal)算法 特点:时间复杂度为O(eloge)(e为网中边数),适合于求稀疏的网的最小生成树。