java图的概念和图的存储
本篇内容主要讲解“java图的概念和图的存储”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“java图的概念和图的存储”吧!
锦江网站制作公司哪家好,找创新互联建站!从网页设计、网站建设、微信开发、APP开发、响应式网站等网站项目制作,到程序开发,运营维护。创新互联建站2013年至今到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联建站。
图的概念和图的存储
图(Graph)是数据结构中最复杂的一种结构,线性表描述的是一对一关系,树描述的是一对多关系,而图描述的是多对多关系。无论是一对一还是一对多,都有一个明确的切入点,而图却不具备这种简单的属性。正因为此,关于图的基础知识也是最多,下面我们就先对这些基础知识进行梳理。
图的概念
图的定义
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V, E),其中 G 表示一个图, V 是图 G 中顶点的集合, E 是图 G 中边的集合。顶点,就是图中的数据元素,边则用来表示数据之间的逻辑关系。顶点是有穷非空的,边则可以为空集。
有向边和无向边
边,根据是否有方向,分为无向边和有向边。无向边指顶点vi到vj之间的边没有方向,用(vi, vj)表示。有向边指顶点vi到vj之间的边有方向,也称作弧,用
左图可以表示为G1 = (V1, {E1}),其中顶点集合V1={A, B, C, D},边集合E1={(A, B), (B, C), (C, D), (D, A), (A, C)}。右图可以表示为G2 = (V2, {E2}),其中顶点集合V2={A, B, C, D},弧集合E2={, ,
有向图和无向图
如果图中任意两个顶点之间的边都是无向边,则称该图为无向图。在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有 n 个顶点的无向完全图有 n(n-1)/2 条边。
同样地,如果图中任意两个顶点之间的边都是有向边,则称该图为有向图。在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有 n 个顶点的有向完全图有 n(n-1) 条边。
如下所示,左图为无向完全图,右侧为有向完全图:
简单图
在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。我们要研究的图都是简单图。如下所示,都不是简单图,不属于我们学习的范畴。
稀疏图和稠密图
有很少条边或弧的图称为稀疏图,反之称为稠密图。这是一个相对的概念。
网
带权的图称为网,权指的是在图的边或弧上的数字,例如下图就是一张带权的图:
子图
假设有两个图G=(V, {E})和G'=(V', {E'}),如果V'∈V且E'属于E,则称G'为G的子图。简言之,就是部分与整体的关系。
顶点与边的关系
对于无向图G=(V, {E}),如果边(v, v')∈E,则称顶点 v 和 v' 互为邻接点,即 v 和 v' 相邻接,边(v, v')依附于顶点 v 和 v',或者说(v, v')与顶点 v 和 v' 相关联。顶点 v 的度是和 v 相关联的边的数目,记为TD(v)。无向图的边的个数和顶点度数的关系如下:
对于有向图G=(V, {E}),如果弧
路径
无向图G=(V, {E})中从顶点 v 到 v' 的路径是一个顶点序列(v=vi,0,vi,1,...,vi,m=v'),其中(vi,j-1,vi,j)∈E,1≤j≤m。
如果是有向图,则路径也是有向的,顶点序列满足
路径的长度是路径上的边或弧的数目。
第一个顶点到最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。
连通图
在无向图G中,如果从顶点 v 到 v' 有路径,则称 v 和 v' 是连通的。如果对于图中的任意两个顶点 vi,vj∈V,vi 和 vj 都是连通的,则称G是连通图。无向图中的极大连通子图称为连通分量。如下图,左图不是连通图,但它有两个连通分量:
在有向图G中,如果对于每一对vi,vj∈V、vi≠vj,从 vi 到 vj 都存在路径,则称G是强连通图。有向图中的极大强连通子图称为有向图的强连通分量。如下图所示,虽然它不是强连通图,但它有两个强连通分量:
生成树和有向树
连通图的生成树是一个极小的连通子图,它含有图中全部的 n 个顶点,但只有足以构成一棵树的 n-1 条边。如下所示,图1是一个连通图,图2和图3都是它的生成树:
n个顶点和 n-1 条边是构成生成树的必要条件,但是它并不充分,如下所示,就不是一个生成树:
如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树。一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。如下图所示,图1就可以拆分成图2和图3两棵有向树。
图的存储
线性表和图都有一个明确的切入点,但是对图而言,每个顶点都可以当做是起点,而且每个顶点之间都可能有逻辑关系,也就是说,单纯的使用数组或链表是无法完成图的存储的。图的存储当前主要有以下五种方式:
1. 邻接矩阵
图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
下面,我们就无向图、有向图和网分别演示邻接矩阵的存储方式。
无向图
其中主对角线的值为0,表示顶点到其本身没有边。无向图的邻接矩阵一定是对称的,也就是以主对角线划分的右上方和左下方对称。从矩阵中我们可以获取以下信息:
判断两个顶点之间是否有边
获取某个顶点的度,只需要求第 i 行或第 i 列的和即可。
获取某个顶点的所有临界点,只需要遍历第 i 行即可。
有向图
有向图的表示和无向图类似,如下所示:
网
因为网的每条边都有权值,所以对应的公式稍有改变,如下所示:
这里∞表示的是不可能出现的值。网的邻接矩阵存储示例如下:
2. 邻接表
数组的优缺点我们都已经熟知,那么使用邻接矩阵就一定会面临空间浪费的问题,上述示例中0或者∞越多,对应图中边数相对于顶点数而言较少时,空间的使用率也就越低。邻接表的思想和哈希表类似,使用数组结合链表的方式来存储图。
无向图
邻接表使用一个数组来存储每个顶点,数组的每一位都包含一个链表,用来存储与此顶点相邻的边,示例如下:
从邻接表中,也可以轻易地获取到顶点、边和度的值。
有向图
有向图的邻接表和无向图类似,但是它获取出度容易,获取入度却比较困难,如下所示:
获取一个顶点的出度只需要计算链表的长度即可,但是入度却没有有效的获取方式,所以通常还会建立一个逆邻接表作为补充,如下所示:
网
用邻接表来存储网的结构只需要增加一个weight字段即可,这里不再演示。
3. 十字链表
邻接表在表示有向图时,需要邻接表和逆邻接表两张表配合使用,较为繁琐,我们可以把邻接表和逆邻接表结合为一张表,这就是十字链表。
十字链表也使用数组来存储顶点,只是每一位数据除了顶点外,还有两个链表分别表示出边表和入边表,数据的结构如下所示:
边表的结构也有所改变,结构如下:
其中,tailvex表示弧起点在顶点表的下标,headvex表示弧终点在顶点表的下标,headlink是入边表指针域,指向下一个终点相同的边,taillink是出边表指针域,指向下一个起点相同的边。
接下来,我们以下图为例,演示十字链表的建立过程:
首先,把全部顶点存储起来,如下所示:
然后,我们建立顶点v0的出边表,可以发现只有
同理,其他顶点的出边表如下:
现在,我们来建立入边表,对于顶点v0,它的入边有两条,分别是
同理建立起其他顶点的入边表,结果如下:
可以看到,十字链表除了结构较为复杂之外,不仅解决了邻接表无法同时获取入度和出度的问题,也没有增加所需的时间复杂度等,因此十分适合有向图的存储。
4. 邻接多重表
十字链表是针对有向图的优化,而邻接表在表示无向图时也存在一定的问题。比如我们要把下图的边(v2, v0)删除,在邻接表中就要删除两个位置:
可以看到,这是因为数据的重复造成的,所以我们可以仿照十字链表的方式构造一个邻接多重表,来解决以上问题。为此,需要重新定义边表结构,如下:
其中,ivex和jvex是某条边依附的两个顶点在顶点表的下标,ilink表示依附于顶点ivex的下一条边,jlink表示依附于顶点jvex的的下一条边。
有了十字链表的经验,构建一个邻接多重表十分容易,我们以上图为例,首先建立好顶点结点和边表结点,如下所示:
这里需要注意的是,边表的每个结点仅出现一次,接下来我们按照规定把这些结点间关系连接起来即可,如下所示:
5. 边集数组
如果我们仅关注边的操作,还可以使用边集数组,它由两个一维数组组成,一个数组用来存储顶点的信息,另一个数组存储边的信息。边的数组的每个元素都由一条边的起点下标、终点下标和权组成。这个存储方式主要用于寻找连通网的最小生成树算法:克鲁斯卡尔算法。
到此,相信大家对“java图的概念和图的存储”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
网页名称:java图的概念和图的存储
URL标题:http://myzitong.com/article/iidosp.html