文档章节

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

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/01/26 19:38
字数 1232
阅读 106
收藏 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



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 142
博文 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
读懂概率图模型:从基本概念和参数估计开始

选自statsbot 作者:Prasoon Goyal 机器之心编译 参与:Panda 概率图模型是人工智能领域内一大主要研究方向。近日,Statsbot 团队邀请数据科学家 Prasoon Goyal 在其博客上分两部分发表了一篇...

机器之心
2017/11/29
0
0
小蚂蚁学习数据结构(3)——线性结构——线性表的链式表示和实现(上)

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

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

没有更多内容

加载失败,请刷新页面

加载更多

关于php的xdebug配置(编辑器vscode)

虽然说echo和print_r是公认的最实用的调试工具,但是效率真的没有可视化的直接断点那么高。这里简单介绍如果安装及配置xdebug for vscode 一、PHP环境处的配置 1、编译安装 下载及编译php,因...

元谷
35分钟前
7
0
heartbeat

http://www.linux-ha.org/doc/users-guide/_building_and_installing_heartbeat_from_source.html kaer@linux-sqlf:~/Reusable-Cluster-Components-glue--0a7add1d9996> ./configure --enabl......

李有常
45分钟前
1
0
shell 脚本 title 免写入

1、有时候写脚本,需要写一些注释信息或者备注之类,当每次都手写比较麻烦,可以写一个脚本,每次运行则自动写入这些信息,不需要在手动输入; 通过 EOF 嵌入文档的方式; [root@localhost_002 sh...

芬野de博客
51分钟前
3
0
FragmentPagerAdapter+ViewPager 更新问题

场景 存在一种需求,当用户系统中,属于某一组织的用户登录之后(或者账户切换),要求主页面显示不同的ViewPager + Fragment组合,并且要求app无需退出就能刷新组合以及组合中的页面。 此外...

IamOkay
52分钟前
3
0
Python有哪些常用的标准库?Python基础教程,第十一讲,常用标准库(一)

上一节课我们学习了如何自定义模块,大家可以定义自己的模块,但是项目中通常不允许我们自己造轮子,所以本节课主要学习Python的标准库,学习使用别人的轮子,由于标准库内容较多,所以我们分...

程序员补给栈
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部