文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 法律资料 > 最小生成树算法及应用
侵权投诉

最小生成树算法及应用

最小生成树算法及应用

最小生成树算法及应用

一、生成树的概念 若图是连通的无向图或强连通的有向图, 若图是连通的无向图或强连通的有向图,则从图中任意一个顶点出发调用一 bfs或dfs后 便可以系统地访问图中所有顶点;若图是有根的有向图, 次bfs或dfs后,便可以系统地访问图中所有顶点;若图是有根的有向图,则从根 出发通过调用一次dfs bfs,亦可系统地访问所有顶点。在这种情况下, dfs或 出发通过调用一次dfs或bfs,亦可系统地访问所有顶点。在这种情况下,图中所 有顶点加上遍历过程中经过的边所构成的子图,称为原图的生成树。 有顶点加上遍历过程中经过的边所构成的子图,称为原图的生成树。 对于不连通的无向图和不是强连通的有向图, 对于不连通的无向图和不是强连通的有向图,若有根或者从根外的任意顶点 出发,调用一次bfs dfs后 一般不能系统地访问所有顶点, bfs或 出发,调用一次bfs或dfs后,一般不能系统地访问所有顶点,而只能得到以出发 点为根的连通分支(或强连通分支)的生成树。要访问其它顶点, 点为根的连通分支(或强连通分支)的生成树。要访问其它顶点,还需要从没有 访问过的顶点中找一个顶点作为起始点,再次调用bfs dfs, bfs或 访问过的顶点中找一个顶点作为起始点,再次调用bfs或dfs,这样得到的是生成 森林。 森林。 由此可以看出,一个图的生成树是不唯一的, 由此可以看出,一个图的生成树是不唯一的,不同的搜索方法可以得到不同 的生成树,即使是同一种搜索方法,出发点不同亦可导致不同的生成树。 的生成树,即使是同一种搜索方法,出发点不同亦可导致不同的生成树。 可以证明:具有n个顶点的带权连通图,其对应的生成树有n 条边。 可以证明:具有n个顶点的带权连通图,其对应的生成树有n-1条边。

最小生成树算法及应用

第1页

你可能喜欢

  • 算法合集
  • 克鲁斯卡尔算法
  • 办公自动化教程
  • 网络模型
  • 教师工资管理系统
  • word2003教案
  • 数据结构课程设计最小生成树

热门文档

相关文档

  • 最小生成树算法及应用

    最小生成树算法及应用一、生成树的概念 若图是连通的无向图或强连通的有向图,则从图中任意一个顶点出发调用一 次bfs或dfs后,便可以系统地访问图中所有顶点;...

  • 最小生成树算法及其应用

    最小生成树算法及应用 17页 免费搜你所想,读你所爱 拒绝盗版,营造绿色文库 如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处...

  • 最小生成树算法及其应用

    703) 摘 要:rsa算 法和 Pm 算法是 求最小 生成 树 的常用 算法,Kukl 文章 设计 了这 两种 算法 的 C语 言程序 , 通过 实例说 明 了算法 的应用 ...

  • 算法合集之《最小生成树算法及其应用》

    IOI2004 国家集训队论文 吴景岳 最小生成树算法及其应用江苏省常州高级中学 吴景岳 【摘要】最小生成树是图论中的经典问题,也是一个重要部分,一般书上 往往只...

  • 最小生成树算法及其应用

    Ju.l 2009 文章编号: 1008 -5564( 2009) 03-0023-04 最小生成树算法及其应用王新奇 1, 2 ( 1. 西安文理学院 学报编辑部, 陕西 西安 710065 ; 2. 西安...

  • 最小生成树算法讲解

    最小生成树算法讲解_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 最小生成树算法讲解_计算机软件及应用_IT/计算机_专业资料。单元...

  • 【论文】最小生成树算法及其应用

    最小生成树是数据结构中图的一种重要应用,对于具有n个...

  • 最小生成树算法(一)

    最小生成树算法(一)_计算机软件及应用_IT/计算机_专业资料。最小生成树算法(一) 包含了最小生成树的原理、相关证明和Prim算法的C实现...

  • 矩阵及最小生成树算法

    矩阵及最小生成树算法_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 矩阵及最小生成树算法_计算机软件及应用_IT/计算机_专业资料。...

  • 【论文】最小生成树算法及其应用

    Kruskal算法和Prim算法是求最小生成树的常用算...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email