小蚂蚁学习数据结构(25)——图的基本概念和术语
小蚂蚁学习数据结构(25)——图的基本概念和术语
嗜学如命的小蚂蚁 发表于2年前
小蚂蚁学习数据结构(25)——图的基本概念和术语
  • 发表于 2年前
  • 阅读 98
  • 收藏 4
  • 点赞 1
  • 评论 2

新睿云服务器60天免费使用,快来体验!>>>   

摘要: 图的基本概念和术语,对图的初步认识

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

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

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

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

图的定义

    图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



标签: 数据结构
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 132
博文 161
码字总数 100864
评论 (2)
首席撸起水泡
佩服佩服,
嗜学如命的小蚂蚁

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

佩服佩服,
×
嗜学如命的小蚂蚁
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: