图的概念及表示

Data Structures - Graph

ZingLix July 26, 2017

基本概念

图(Graph)是一种表示物件和物件之间关系的方法,是图论的基本研究对象,由顶点(Vertex)和边(Edge)组成。

1.jpg

如图所示即为一个最基本的图,小圆点即为顶点,连接顶点的线即为边。通常以 \(\vert V \vert\) 来表示顶点数量,\(\vert E \vert\) 代表边的数量。当两个顶点中存在直接相连的边则称这两个点邻接(adjacent)。

图有如下几种类别。

类别 定义
有向图 图中每一条边都被规定一个方向,则为有向图,边被称为有向边。
无向图 与有向图相反,如果边没有规定方向则为无向图。
简单图 图中每两个顶点(有向图则是每个方向)最多只有一条边,并且顶点不连向自己。
多重图 允许图中两个顶点间有多于一条的边,而且边可以连接同一个顶点。
基础图 对于一个有向图,去除其边上方向的图则为该有向图的基础图。
连通图 如果一个无向图中,每个点到其他每一个点有一条路径,则为连通的(connected)。
强连通图 对于有向图,若满足连通图性质则为强连通的(strongly connected)。
弱连通图 对于不是强连通的有向图,如果其基础图(Underlying Graph)为连通的,则为弱连通(weakly connected)。
完全图 每两个结点之间如果都存在一条边则称为完全图(Complete Graph)。

邻接矩阵

邻接矩阵(Adjacency Matrix)是一个大小为 \(\vert V \vert \vert V \vert\) 的二维数组。将顶点进行编号,从 0 到 n ,则对于 \(Adj[i][j]\) ,则代表第 i 个顶点到第 j 个顶点的边。对于无权重的图,值为 0 代表不存在这条路,1 则代表存在这条路。对于有权重的图,则可以用具体权重大小来代替无权重图中的 1 。

AdjMat.jpg

对于无向图而言,邻接链表表示法可以只要求一半的存储空间,因为对于无向图的邻接矩阵而言,其转置即为其本身。

邻接链表

邻接链表(Adjacency List)由 \(\vert V \vert\) 个链表组成,每一个表头为一个顶点,链表中每个节点则为与表头顶点相连的顶点,并同时记录着边权重大小。

AdjList.jpg

比较

两种表示方法都可以很好的表示一张图,但是邻接链表无法快速给出两个顶点间边的性质,相对而言邻接矩阵很好的克服了这一问题,但同时付出了更大的存储空间作为代价。 所以一般而言,在图的规模较小的情况下,更倾向于用邻接矩阵的方式来表示。

图片和gif根据 visualgo.net 制作