算法快学笔记（十）：截图“图”的面纱

1. 介绍

数据结构领域，图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。

本文对图的基础支持做一个简单的总结。

2. 定义

2.1 图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

2.2 图的分类

2.2.1 有向/无向/完全

按照方向分为无向图和有向图。

上图中，左图为无向图是由顶点和边构成，右图为有向图是由顶点和弧（有向边构成）。弧有弧头和弧尾区别。

在用数学方式表示时，无向边用()表示，有向边用<>表示。现在我们讲解的图全是简单图。

如果任意两个顶点之间都存在边叫完全图，有向的边叫有向完全图。如果无重复的边或者顶点到自身的边叫简单图。上图左侧为简单图

有些图的边或弧具有与它相关的数字，这种带权的图通常称为网，下面就是一个带权的图

• 无向图：顶点的边数是度
• 有向图：
  • 入度：方向指向顶点的边；
  • 出度：方向背向顶点的边。
  • 顶点的度=出度+入度。

2.5 路径长度

路径的长度是路径上边或是弧的数目。对于相同的两个顶点，不同的路径可能会有不同的路径长度。

上图中,左侧路径的长度为2,右侧路径的长度为3

2.6 连通

• 无向图：任意两个顶点是相通的就是连通图。下图中，左侧为非连通的，右侧为连通的

  

• 有向图：任意两个顶点是相通的就是强连通图，下面左侧的图中，不存在D->A不是连通的，所以不是强连通图，而右侧的则为强连通图。

  

3. 图的存储

图的结构比价复杂，任意两个顶点之间都可能存在关系，不能用简单的顺序存储结构来表示。如果运用多重链表，即一个数据域多个指针域组成的结点表示图中一个结点，则造成大量存储单元浪费。

3.1 邻接矩阵

邻接矩阵用两个数组保存数据。一个一维数组存储图中顶点信息，一个二维数组存储图中边或弧的信息，结构如下。

邻接矩阵表示带权图的方法如下：

带权图值的说明如下：

1. 0：在主对角线上表示指向自己，否则表示权值
2. 无穷大：表示两个顶点不通
3. 权值

特点：

1. 0表示无边，1表示有边
2. 顶点的度是行内数组之和。
3. 求取顶点邻接点，将行内元素遍历下。
4. 无向图：无向图中二维数组是个对称矩阵
5. 有向图：各行之和是出度，各列之和是入度。

缺点：邻接矩阵对于边数相对顶点较少的图，就是对存储空间极大的浪费。

3.2 邻接表

邻接表：数组和链表相结合的存储方法为邻接表。

存储结构如下：

• 图中顶点用一个一维数组存储。
• 图中每个顶点的所有邻接点构成一个线性表。

从图中得知，顶点表的各个结点由data和Firstedge两个域表示，data是数据域，存储顶点信息，firstedge是指针域，指向边表的第一个结点，即顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中坐标，next存储边表中下一个结点指针。比如v1顶点与v2、v0互为邻接点，则在v1边表中，adjvex分别为0和2。

有向图也可以用邻接表，出度表叫邻接表，入度表尾逆邻接表。

3.3 十字链表

在邻接表中针对有向图，分为邻接表和逆邻接表，导致无法从一个表中获取图的入读和出度的情况，于是诞生了十字链表,相关结构如下：

1. 顶点结构

• firstin：入边表头指针，指向顶点入边表的第一个结点。

• firstout：出边表头指针，指向顶点出边表第一个结点。

2. 边结构

• tailvex是指弧起点在顶点表的下标
• headvex弧终点在顶点表的下标
• headlink入边表指针域，指向终点相同的下一条边
• taillink是指边表指针域，指向起点相同的下一条边。

示例如下：

十字链表把邻接表和逆邻接表整合在了一起，便于统计顶点的出度和入度，且算法的时间复杂度和邻接表相同。

3.4 邻接多重表

如果使用邻接存储无向图，操作顶点很方便，但是对于边的操作比较麻烦（例如删除边），使用邻接多重表可以解决该问题，邻接多重表的边结构的定义如下：

ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附项点ivex的下一条边，jlink指向依附顶点jvex的下一条边。

3.5 边集数组

边集数组由两个一位数组构成，一个用来存储顶点信息，一个用来存储边信息。边集数组关注的重点是对边的操作，比较适合一次对边进行处理的操作，如果想要获取某个顶点的度可能就不大适合。

边的结构表示为：

例子如下：