文档章节

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

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



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 137
博文 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
【编译】理解这25个概念,你的「深度学习」才算入门!

【导览】:很多人认为深度学习很枯燥,大部分情况是因为对深度学习的学术词语,特别是专有名词很困惑,即便对相关从业者,亦很难深入浅出地解释这些词语的含义。本文编译自Analytics Vidhya,...

Major术业
2017/05/27
0
0
读懂概率图模型:从基本概念和参数估计开始

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

机器之心
2017/11/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

iOS开发用到的图片尺寸汇总

启动图 型号 竖屏 横屏 iPhone SE 640px × 1136px 1136px × 640px iPhone 6s 750px × 1334px 1334px × 750px iPhone 6s Plus 1242px × 2208px 2208px × 1242px iPhone 7 750px × 1334......

业界小白
21分钟前
0
0
浅谈redis

redis是一个开源,内存式的健值存储数据库,也被称为健值存储的字典服务器。健值类型有字符串,hash(哈希类型),set(集合),list(列表) 和有序集合 特征细节: 内存式:redis将健值存储在主...

拐美人
29分钟前
0
0
无限扩容,按需使用!ZStack推出基于阿里云NAS的文件存储服务

日前,ZStack发布2.6.0版本,正式宣布推出基于阿里云NAS的文件存储服务。得益于业界领先的阿里云分布式存储架构,融合NAS后的ZStack 2.6.0拥有高性能、高可靠、容量无限扩展、一键操作、按需...

ZStack社区版
31分钟前
1
0
崛起于Springboot2.X之Mongodb多数据源处理(35)

多数据源:4个mongodb库! 目录结构图: 1、添加pom依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-mongodb</artifactId>......

木九天
37分钟前
0
0
如何获取显示器的EDID信息

Q1: 为什么要写这篇文章? A1:在最近的工作中遇到了不少问题,其中很多都是和EDID相关的。可以说,作为一家以“显示”为生的企业,我们时时刻刻在与EDID打交道。EDID这东西很简单,但是如果...

DB_Terrill
37分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部