文档章节

小蚂蚁学习数据结构(25)——图的基本概念和术语

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/01/26 19:38
字数 1232
阅读 105
收藏 4

图是一种较线性表和树更为复杂的非线性结构。

在线性结构中,结点之间的关系,除开始结点和终端结点外,每个结点只有一个直接前驱和直接一个后继。

在树形结构中,结点之间的关系实质上是层次关系,同层上的每个结点可以和下一层的零个或多个结点相关,但只能和上一层的一个节点相关(除了根节点)。

在图形结构中,对结点(一般称为顶点)的前驱和后继的个数都是不加限制的,即结点之间的关系是任意的。图中任意两个结点之间都可能相关。

图的定义

    图G有两个集合V和E组成,记作 G = (V,E)

    V是顶点的有穷非空集合,E是v中顶点偶对的有穷集合。

    这些顶点偶对称为边。通常V(G)和E(G)分别称为图的顶点集合和边集合。

    E(G)可以为空集。

有向图

    对一个图G,若边的集合E(G)是有向边的集合,则称该图为有向图。即顶点之间的连线是有方向的。

    其中<x,y>表示从x到y的一条弧,x是弧尾,y为弧头

无向图:

    对于一个图G,若边的集合E(G)是无向边的集合,这个图就是无向图。即顶点之间的连线是没有方向的。

    其中,(x,y)表示x与y之间的一条连线,称为边。

已知顶点数n,求边或者弧的条数

    无向图:0 <= e <= n(n-1)/2

    有向图:0 <= e <= n(n-1)

    推导过程:

        对有向图,每个顶点至多有n-1条边与其相连,n个顶点最多就有n(n-1)条边。

        但是无向图,每条边连接两个顶点,所以除去一半,故n(n-1)/2

其他术语

    端点和邻接点

        在一个无向图中,若存在一条边<v1,v2>,则称v1和v2就是该边的两个端点,并称他们为领接点

    无向完全图

        在一个无向图中,如果任意两顶点都有一条直接边相连接,则称该图为无向完全图。

    有向完全图

        在一个有向图中,如果任意两顶点都有方向互为相反的两条弧相连接,则称该图为有向完全图。

    

这一节的概念真多,我都不想写了。

        

顶点的度、入度、出度:顶点的度是指依附于某顶点v的边数。

       在有向图中,要区别顶点的入度和出度的概念。顶点v的入度是指以顶点v为终点的弧的数目。顶点v的出度是指以顶点v为始点的弧的数目。

边的权、网:

    权:与边相关的数据信息成为权weight。在实际应用中,权值可以有某种含义。边上带权的图称为网。

路径、路径长度:

    从顶点u能都走到顶点w,之间的距离就是路径。

    路径上边的数目成为路径长度。

    简单路径:序列中顶点不重复出现的路径。

    回路、环(cycle):路径中第一个顶点和最后一个顶点相同的路径。

    简单回路、简单环:除了第一个顶点与最后一个顶点之外,其他顶点不重复出现的回路称为简单回路,或者简单环。

子图:图中的一部分,称为子图。

连通的、连通图、连通分量:

    在无向图中,如果从一个顶点vi到另一个顶点vj有路径,这称vi和vj是连通的。

    如果图中任意两顶点都是连通的,这称该图为连通图。

    无向图的极大连通子图称为连通分量。

强连通图、强连通分量: 

    对于有向图来说,若图中任意一对顶点vi和vj均有从一个顶点vi到另一个顶点vj有路径,也有从vj到vi的路径,则称该有向图是强连通图。

    有向图的极大强连通子图称为强连通分量。

生成树:

    所谓连通图G的生成树,是G的包含其全部n个顶点的一个极小连通子图。必定包含G的n-1条边。多增加一条边,就会产生回路,少一条边,就成了非连通图。

生成森林:

    在非连通图中,由每个连通分量都可得到一个极小连通子图,及一颗生成树。

    这些连通分量的生成树就组成了一个连通图的生成森林。


    学PHP的小蚂蚁 博客 http://my.oschina.net/woshixiaomayi/blog



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 138
博文 161
码字总数 100864
作品 0
郑州
程序员
加载中

评论(2)

嗜学如命的小蚂蚁
嗜学如命的小蚂蚁

引用来自“首席撸起水泡”的评论

佩服佩服,
首席撸起水泡
首席撸起水泡
佩服佩服,
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
小蚂蚁学习C语言(30)——C语言初识链表(上)

链表,c语言和数据结构的一个连接 算法: 通俗定义: 解题的方法和步骤 狭义定义: 对存储数据的操作,对不同的存储结构要完成某一个功能所执行的操作是不一样的 比如,要输出数组中所有元素...

嗜学如命的小蚂蚁
2015/12/26
76
0
【数据平台】python语言NLP库Gensim初识

1、基本介绍 Gensim是一款开源的第三方Python工具包,用于从原始的非结构化的文本中,无监督地学习到文本隐层的主题向量表达。它支持包括TF-IDF,LSA,LDA,和word2vec在内的多种主题模型算法...

fjssharpsword
2017/11/01
0
0
Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

JAVA高级架构开发
10/07
0
0
小蚂蚁学习数据结构(3)——线性结构——线性表的链式表示和实现(上)

通过上篇对线性表的顺序表示和实现可以知道,在顺序存储结构的线性表中对某个元素的插入和删除,其时间主要耗费在移动元素上,而移动元素的个数取决于插入和删除元素的位置。 这句话我是在书...

嗜学如命的小蚂蚁
2015/12/31
86
0

没有更多内容

加载失败,请刷新页面

加载更多

TypeScript基础入门之声明合并(二)

转发 TypeScript基础入门之声明合并(二) 声明合并 合并命名空间 与接口类似,同名的命名空间也将合并其成员。 由于名称空间同时创建了名称空间和值,因此我们需要了解它们是如何合并的。 要合...

durban
24分钟前
0
0
centos7系统安装sersync+rsync实现服务器同步功能

centos7系统安装sersync+rsync实现服务器同步功能 MQ_douer0人评论21708人阅读2017-04-08 15:49:03 一、为什么要用sersync+rsync架构? 1、sersync是基于inotify开发的,类似于inotify-tools...

linjin200
24分钟前
1
0
Windows下安装phpRedis扩展

Windows下安装phpRedis扩展 通常在做PHP程序测试时,会用到Redis。而一般测试都是在Windows下进行的,所以需要在Windows环境下安装phpRedis扩展,用以支持php对Redis的访问。 工具/原料 php调...

梦梦阁
29分钟前
1
0
HTTPConnectionPool(host:XX)Max retries exceeded with url 解决方法

HTTPConnectionPool(host:XX)Max retries exceeded with url 解决方法 在做双十一压测时,高并发调用requests时报错.问题解决方法 问题原因 是因为在每次数据传输前客户端要和服务器建立TCP...

_Change_
33分钟前
0
0
iosdfgh

复制 IO流 (***** 了解 *****) 1.1 概述 之前我们学习了 File 类,这个类中有很多操作文件本身的方法, File类它只能操作文件或文件夹,并不能去访问文件中的数据。真正保存数据的是文件,数据...

码农屌丝
35分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部