博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
图的理解:基本概念
阅读量:5745 次
发布时间:2019-06-18

本文共 1037 字,大约阅读时间需要 3 分钟。

图的基本概念

图是什么,图是一种数据结构,一种非线性结构,所谓的非线性结构,浅显地理解的话,就是图的存储不是像链表这样的线性存储结构,而是由两个集合所组成的一种数据结构。

一个图中有两类东西,一种是结点,一种结点之间的连线。要用一种数据结构来表示的话,首先我们需要一个集合来存储所有的点,我们用V这个集合来表示(vertex),还需要另一个集合来存储所有的边,我们用E来表示(Edge),那么一个图就可以表示为:

G = (V,E)

有的图的边是有方向的,有的是没有方向的。

(A,B)表示A结点与B结点之间无方向的边,<A,B>则表示方向为从A到B的一条边,当然,如果是<B,A>,则方向相反。因此从边的方向我们就可以把图分为有向图无向图两种。

其它概念

一个图中的元素有很多,例如:

完全图,邻接节点,结点的度,路径,权,路径长度,子图,连通图和强连通图,生成树,简单路径和回路...

本文只说说容易混淆的概念,以后再慢慢写。

完全图,连通图,与强连通图

完全图可分为有向完全图和无向完全图两种,如果一个图的任意两个结点之间有且只有一条边,则称此图为无向完全图,若任意两个结点之间有且只有方向相反的两条边,则称为有向完全图。

那么连通图与完全图有什么区别呢?连通图是指在无向图中,若图中任意一对结点之间都有路径可达,则称这个无向图是连通图,而强连通图则是对应于有向图来说的,其特点与连通图是一样的。只不过是有向的,所以加了"强"。

连通图与完全图的区别就是,完全图要求任意两点之间有边,而连通图则是要求有路径。边和路径是有区别的。

邻接结点

一个结点的邻接节点,对于无向图来说,就是与这个结点相连的结点,至少有一个。

对于有向图来说,由于边是有方向的,所以一个结点的邻接节点是指以这个结点为开头,所指向的那些结点。

结点的度

度是针对结点来说的, 又分为出度和入度,看到“出度入度”,我们不难想到这是与边和边的方向有关的。

对于无向图来说,没有出度入度之分,一个结点的度就是经过这个结点的边的数目(或者是与这个结点相关联的边的数目),对于有向图来说,出度就是指以这个结点为起始的边的条数(箭头向外),入度则是以这个点为终点的边的条数(箭头向内)。

出 = 箭头向外,入 = 箭头向内

权是指一条边所附带的数据信息,比如说一个结点到另一个结点的距离,或者花费的时间等等都可以用权来表示。带权的图也称为网格或网。

子图

跟一个集合有子集一样,图也有子图。可以类比理解。

扫一扫关注我的微信公众号

转载地址:http://aeizx.baihongyu.com/

你可能感兴趣的文章
d3 v4实现饼状图,折线标注
查看>>
微软的云策略
查看>>
Valid Parentheses
查看>>
windows下Python 3.x图形图像处理库PIL的安装
查看>>
【IL】IL生成exe的方法
查看>>
没有JS的前端:体积更小、速度更快!
查看>>
数据指标/表现度量系统(Performance Measurement System)综述
查看>>
GitHub宣布推出Electron 1.0和Devtron,并将提供无限制的私有代码库
查看>>
论模式在领域驱动设计中的重要性
查看>>
四、配置开机自动启动Nginx + PHP【LNMP安装 】
查看>>
Linux 目录结构及内容详解
查看>>
OCP读书笔记(24) - 题库(ExamD)
查看>>
.net excel利用NPOI导入oracle
查看>>
$_SERVER['SCRIPT_FLENAME']与__FILE__
查看>>
hive基本操作与应用
查看>>
html5纲要,细谈HTML 5新增的元素
查看>>
Android应用集成支付宝接口的简化
查看>>
[分享]Ubuntu12.04安装基础教程(图文)
查看>>
django 目录结构修改
查看>>
win8 关闭防火墙
查看>>