有向图和无向图的相关概念

图的定义:

  图在数据结构中是中一对多的关系,一般分为无向图与无向图

  常用 邻接矩阵 或者 邻接链表 来表示图中结点的关系


完全图/稠密图/稀疏图:

  ⑴具有n个顶点,n(n-1)/2条边的图,称为完全无向图,

  ⑵具有n个顶点,n(n-1) 条弧的有向图,称为完全有向图。

  ⑶完全无向图和完全有向图都称为完全图。

  ⑷对于一般无向图,顶点数为n,边数为e,则 0≤e  ≤n(n-1)/2。

  ⑸对于一般有向图,顶点数为n,弧数为e, 则 0≤e≤n(n-1)  。

  ⑹当一个图接近完全图时,则称它为稠密图,

  ⑺当一个图中含有较少的边或弧时,则称它为稀疏图。


完全图

连通图:如果一个无向图从每一个顶点到其他顶点都存在一条路径,则称该无向图为连通图

强连通图:具有这样的性质的有向图称为是强连通的,如果不是强连通的,

弱连通图:它的基础图,即去掉弧上的方向所形成的的图,是连通的,那么该有向图称为弱连通的

完全无向图:具有n个顶点,并具有n(n - 1)/2 条边的图,称为完全无向图(每个顶点到其他顶点都有边),连通图

完全有向图:具有n个顶点,并且具有n(n - 1) 条边的有向图,称为完全有向图(每个顶点到其他顶点都有相互两条边),强连通图

完全图:完全无向图和完全有向图都称为完全图


网友评论

0条评论

发表

网友评论

0条评论

发表

最新评论

推荐文章

彩龙

Copyright © 2008-2020 彩龙社区(https://www.clzg.cn) 版权所有 All Rights Reserved.

免责声明: 本网不承担任何由内容提供商提供的信息所引起的争议和法律责任。

经营许可证编号:滇B2-20090009-7

下载我家昆明APP 下载彩龙社区APP