文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 图论中的常用经典算法
侵权投诉

图论中的常用经典算法

图论中的常用经典算法

第一节 最小生成树算法

一、生成树的概念

若图是连通的无向图或强连通的有向图,则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点;若图是有根的有向图,则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下,图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。

对于不连通的无向图和不是强连通的有向图,若有根或者从根外的任意顶点出发,调用一次bfs或dfs后不能系统地访问所有顶点,而只能得到以出发点为根的连通分支(或强连通分支)的生成树。要访问其它顶点则还需要从没有访问过的顶点中找一个顶点作为起始点,再次调用bfs或dfs,这样得到的是生成森林。

由此可以看出,一个图的生成树是不唯一的,不同的搜索方法可以得到不同的生成树,即使是同一种搜索方法,出发点不同亦可导致不同的生成树。如下图:

图论中的常用经典算法

但不管如何,我们都可以证明:具有n个顶点的带权连通图,其对应的生成树有n-1条边。

二、求图的最小生成树算法

严格来说,如果图G=(V,E)是一个连通的无向图,则把它的全部顶点V和一部分边E’构成一个子图G’,即G’=(V, E’),且边集E’能将图中所有顶点连通又不形成回路,则称子图G’是图G的一棵生成树。

对于加权连通图,生成树的权即为生成树中所有边上的权值总和,权值最小的生成树称为图的最小生成树。

求图的最小生成树具有很高的实际应用价值,比如下面的这个例题。

第1页

你可能喜欢

  • 最小费用流
  • 图论算法
  • 数据结构算法
  • 图论及其应用
  • 经典算法
  • 计算几何常用算法
  • c语言常用算法
  • 常用数字滤波算法

热门文档

相关文档

  • java实现图论中的经典算法

    java实现图论中的经典算法_计算机软件及应用_IT/计算机_专业资料。java实现的... 图论中的常用经典算法 25页 2下载券 图论算法(经典) 23页 1下载券 经典...

  • 经典图论算法

    图论中的常用经典算法第一节一、生成树的概念若图是连通的无向图或强连通的有向图,则从其中任一个顶点出发调用一次 bfs 或 dfs 后便 可以系统地访问图中所有...

  • 图论算法(经典)

    图论算法习题 网络建设问题 最短变换问题 挖地雷 乌托邦城市 乌托邦交通中心 某大学准备在校园网中构建校园网络,已知在校园网中选好了 N(N<1000)个点,并准备在 ...

  • 图论算法

    图论算法_工学_高等教育_教育专区。此为数学建模中图论算法中的经典算法距离矩阵 load data.txt; length=length(data); for i=1:length ii=data(i,1); jj...

  • 图论算法

    图论算法(经典) 23页 1财富值 经典图论算法 22页 2财富值 图论算法 12页 ...第三章 拓扑排序(A0V 网) 3.1AOV 网 在现代化管理中, 人们常用有向图来...

  • 图论的基本算法

    图论中的常用经典算法 22页 2下载券 图论基础 27页 免费 图论算法 41页 免费 图论及其应用 58页 1下载券图论的基本算法...

  • 图论算法

    图论的基本算法及应用 60页 1下载券 图论算法(经典) 23页 1下载券...重复(2) ,直到 v∈S Dijkstra算法的举例: 算法的举例: 算法的举例 求图中...

  • 图论的算法

    图论算法(经典) 23页 1财富值 图论相关算法 125页 2财富值喜欢此文档的还...? E中每个元素e是连接顶点集 V中两个顶点u和v的边。 图G=<V,E>: 点集...

  • 图论 第四讲 经典算法

    图论 第四讲 经典算法_数学_自然科学_专业资料。图论的经典算法图的经典算法...与 PRIM 的不同: Kruskal 算法在森林中的两棵树之间 添安全 边; Prim 算法...

  • 图论及其算法

    图论及其算法_理学_高等教育_教育专区。图论及算法...图与网络是运筹学(Operations Research)中的一个经典...这里我们介 绍计算机上用来描述图与网络的5 种常用...

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