博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
图的连通性——无向图的连通分量和生成树
阅读量:5861 次
发布时间:2019-06-19

本文共 464 字,大约阅读时间需要 1 分钟。

hot3.png

1.首先举个实例来说明连通性,看下图:

图G1

 

上图为非连通图,对上图的连接表进行深度优先搜索遍历,3次调用DFS过程,分别从顶点A,D,G出发,得到的顶点访问序列为:

A L M J B F C     D E   G I K H

上面的3个顶点集和所有依附于这些顶点的边,便构成了非连通图的3个连通分量。

2.设E(G)为连通图G中所有边的集合,则从图中任一顶点出发遍历图时,必定将E(G)分成两个集合T(G)和B(G),其中T(G)是遍历图过程中历经的边的集合;B(G)是剩余边的集合。显然T(G)和图中所有的顶点一起构成连通图G的极小连通子图,又成为连通图的一颗生成树,并且称由深度优先搜索得到的为深度优先生成树;由广度优先搜索得到的为广度优先生成树。

对于非连通图,每个连通分量中的顶点集,和遍历走过的边一起构成若干颗生成树,这些连通分量的生成树组成非连通图的生成树林。

上图G1的深度优先生成树林为:

3.深度优先生成森林的算法

 

转载于:https://my.oschina.net/u/2263272/blog/1610088

你可能感兴趣的文章
Eclipse配置python环境
查看>>
晶振不起振的原因及其解决方法
查看>>
《系统架构师》——操作系统和硬件基础
查看>>
如何看待一本图书
查看>>
oracle参数列表
查看>>
Linux 中如何通过命令行访问 Dropbox
查看>>
开发进度——4
查看>>
JS里验证信息
查看>>
Akka actor tell, ask 函数的实现
查看>>
windows10 chrome 调试 ios safari 方法
查看>>
Hello , Ruby!
查看>>
Netty 4.1.35.Final 发布,经典开源 Java 网络服务框架
查看>>
详解Microsoft.AspNetCore.CookiePolicy
查看>>
SCDPM2012 R2实战一:基于SQL 2008 R2集群的SCDPM2012 R2的安装
查看>>
SQL SERVER中字段类型与C#数据类型的对应关系
查看>>
Linux lsof命令详解
查看>>
SVG path
查看>>
js判断checkbox是否选中
查看>>
多系统盘挂载
查看>>
MySQL函数怎么加锁_MYSQL 函数调用导致自动生成共享锁问题
查看>>