未加星标

图的基本概念和表示

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二03 | 时间 20160901 | 作者 红领巾 ] 0人收藏点击收藏

基本概念

一个图(graph)G=(V,E)由顶点(vertex)的集V和边(edge)的集E组成。每一条边就是一副点对(v,w),其中v、w V。有时也把边称做弧(arc)。

有向(directed):如果点对是有序的,那么图就是有向的。

有向图(digraph):有向的图有时也叫有向图。路径u,v,u可以被认为是圈,因为(u,v)和(v,u)不是同一条边。

无向图:与有向图相对,我们要求边是互异的。这些要求的根据在于无向图中的路径u,v,u不应该被认为是圈,因为(u,v)和(v,u)是同一条边。

邻接(adjacent):顶点w和v邻接当且仅当(v,w) E。在一个具有边(v,w)从而具有边(w,v)的无向图中,w和v邻接且v也和w邻接。

权(weight)或值(cost):边具有的第三种成分。

路径(path):图中的路径是一个顶点序列w1,w2,w3,…,wN使得(wi,wi+1) E,1 ≤ i < N。

路径的长(length):路径上的边数。从一个顶点到它自身可以看成是一条路径,如果路径不包含边,那么路径的长为0。

环(loop):如果图含有一条从一个顶点到它自身的边(v,v),那么路径v,v有时也叫做环。

简单路径:一条简单路径是这样一条路径,其上的所有顶点都是互异的,但第一个顶点和最后一个顶点可能相同。

圈(cycle):有向图中的圈是满足w1=wN且长至少为1的一条路径。

简单圈:满足圈的定义,并且如果该路径是简单路径,那么这个圈就是简单圈。

无圈的(acyclic):如果一个有向图没有圈,则称其为无圈的。一个有向无圈图有时也简称为DAG。

基础图(underlying graph):图中其弧去掉方向所形成的图。

连通的(connected):如果在一个无向图中从每一个顶点到每个其它顶点都存在一条路径,则称该无向图是连通的。

强连通的(strongly connected):先是连通的,然后具有这样性质的有向图称其为强连通的。

弱连通的(weakly connected):如果一个有向图不是强连通的,但是它的基础图,即其弧上去掉方向所形成的图,是连通的,那么该有向图称为是弱连通的。

完全图(complete graph):完全图是其每一对顶点间都存在一条边的图。

图的表示

一个有向图:

图的基本概念和表示

图中有7个顶点和12条边。

表示图的一种简单的方法是使用一个二维数组,称为邻接矩阵(adjacent matrix)表示法。对于每条边(u,v),置A[u][v]等于true;否则,数组的元素就是false。如果边有一个权,那么可以置A[u][v]等于该权,而使用一个很大或者很小的权作为标记表示不存在的边。

虽然这样表示的优点是非常简单的,但是,它的空间需求则为θ(|V|2),如果图的边不是很多,那么这种表示的代价就太大了。若图是稠密(dense)的:|E|=θ(|V|2),则邻接矩阵是合适的表示方法。

如果图不是稠密的,换句话说,如果图是稀疏的(sparse),则更好的解决方法是使用邻接表(adjacency)表示。对每一个顶点,我们使用一个表存放所有邻接的顶点。此时的空间需求为O(|E|+|V|),它相对于图的大小而言是线性的。如果边有权,那么这个附加信息也可以存储在邻接表中。

图的邻接表表示法:

图的基本概念和表示

邻接表是表示图的标准方法。无向图可以类似地表示,每条边(u,v)出现在两个表中,因此空间的使用基本上是双倍的。在图论算法中通常需要找出与某个给定顶点v邻接的所有的顶点。而这可以通过简单地扫描相应的邻接表来完成,所用的时间与这些找到的顶点的个数成正比。

有几种方法保留邻接表。首先注意到,这些邻接表本身可以被保存在任何种类的List,即ArrayList或LinkedList中。然而,对于非常稀疏的图,当使用ArrayList时程序员可能需要从一个比默认容量更小的容量开始ArrayList。否则可能造成明显的空间浪费。

因为关键在于能够迅速得到与任一顶点邻接的那些顶点的表,所以两个基本的选择是,或者使用一个映射,在这个映射下,关键字就是那些顶点而它们的值就是那些邻接表,或者把每一个邻接表作为Vetex类的数据成员保存起来。这第1个选择论证要简单,而第2个选择可能会更快,因为它避免了在映射下的重复查找。

在第2种情形,如果顶点是一个String,那么可以使用映射,在映射下,关键字是顶点名而关键字的值则是一个Vertex,并且每一个Vertex对象拥有一个邻接顶点表,或许还有原始的String串名。

本文地址:http://www.linuxidc.com/Linux/2016-09/135310.htm


图的基本概念和表示

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

主题: 算法程序员Linux数据需求
分页:12
转载请注明
本文标题:图的基本概念和表示
本站链接:http://www.codesec.net/view/483476.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(19)