前言：

图计算在数据科学中占据了很重要的地位，例如内存计算大数据框架Spark的数据对象就是采用图计算的方式； 旅游大数据中游客最佳路线选择也是采用图计算，等等。

一、图的相关概念

1、图的定义

图是由顶点和边组成的集合，通常用 G = ( V , E )来表示，其中V是所有顶点组成的集合，而E代表所有边所组成的集合。图的种类有2种：一种是无向图，一种是有向图，无向图以（V1 , V2）表示其边，而有向图以< V1,V2>表示其边

2、无向图

无向图是一种边没有方向的图，即同边的两个顶点没有次序关系，例如(V1,V2)与(V2,V1)代表的是相同的边，如图所示：

V = {A,B,C,D,E}

E = {(A,B),(A,E),(B,C),(B,D),(C,D),(C,E),(D,E)}

接下来介绍无向图的重要术语：

（1）完全图：在“无向图”中，N个顶点正好有N(N-1)/2条边，则称为“完全图”，如图所示

（2）路径：对于从顶点Vi到Vj的一条路径，是指由所经过顶点组成的连续数列，如上图中，V1到V5的路径有{(V1,V2)、(V2,V5)}以及{(V1,V2)、(V2,V3)、(V3,V4)、(V4,V5)}等等

（3）简单路径：除了起点和终点可能相同外，其它经过的顶点都不同，也就是说如果一条路径上顶点不重复出现

（4）路径长度：是指路径上所包含边的总数，在上图中（V1,V2）、(V2,V3)、(V3,V4)、(V4,V5)是一条路径，其长度为4，且为一条简单路径

（5）回路：起始顶点和终止顶点为同一个点的简单路径称为回路。例如上图：{(V1,V2)、(V2,V4)、(V4,V5)、(V5,V3)、(V3,V1)}的起点和终点都是A，所以是一个回路

（6） 关联（Incident）：如果Vi与Vj相邻，我们则称(Vi,Vj)这个边关联顶点Vi和顶点Vj，关联顶点V2的边有（V1,V2）、(V2,V4)、(V2,V5)、(V2,V3)

（7）子图，例如：

（8）相邻（adjacent）：如果（Vi,Vj）是E(G)中的一边，则称Vi和Vj相邻

（9）连通分支（connected component）：在无向图中，相连在一起的最大子图，例如上图有2个联通分支

（10）度数：在无向图中，一个顶点所拥有边的总数为度数，例如上图V1的度数为4

3、有向图

有向图是一种每一条边都可是使用有序对<V1,V2>来表示图，并且<V1,V2>与<V2,V1>是表示两个方向不同的边，而所谓<V1,V2>，是指V1为尾端指向为头部的V2，如下图：

V = {A, B , C , D,E}

E ={<A,B>,<B,C>,<C,D>,<C,E>,<E,D>,<D,B>}

有向图的相关定义

（1）完全图：具有n个顶点且恰好有n*(n-1)个边的有向图，如下图所示：

（2）路径：有向图从顶点Vp到顶点Vq的路径是指一串从顶点所组成的连续有向序列

（3）强连通：有向图中，如果每个成对顶点Vi,Vj有直接路径（Vi和Vj不是同一个点），同时有另一条路径从Vj到Vi，则称此图为强连通图，如下图所示：

（4）强连通分支：有向图中构成强连通的最大子图，在下图（a）是强连通，但(b)不是强连通，如图所示：

而图（b）中的强连通分支如图所示：

（5）出度数：是指有向图中，以顶点V为箭尾的边数

（6）入度数：是指有向图中，以顶点V为箭头的边数，如下图：

V4的入度数是1，出度数是0 ； V2的入度数是4，出度数是1

二、图的数据表示法

1、邻接矩阵法

图A有n个顶点，以n x n的二维矩阵来表示，此矩阵的定义为：对于一个图G = (V,E)，假设有n个顶点，n >= 1，则可以将n个顶点的图，使用一个n x n的二维矩阵来表示，其中假设A(i , j) = 1，则表示图中有一条边( Vi , Vj)存在，反之， A(i , j) = 0，则不存在边A(i , j)

相关特性：

（1）对于无向图而言，邻接矩阵一定是对称的，而且对角线一定为0，有向图则不一定如此

（2）在无向图中，任一节点i的度数为

，就是第 i “行”所有元素的和 ；在有

向图中，节点 i 的出度数为

，就是第 i 行所有的元素的和，而入度数为

，就是第j 列所有的元素的和

（3）用邻接矩阵法表示图共需n x n个单位 空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线全部为零外，仅需存储上三角或下三角的数据即可，因此仅需n(n – 1 )/2的单位空间

示例-1：使用邻接矩阵表示下列“无向”图

得到下列邻接矩阵：

而对于有向图，邻接矩阵则不一定是对称矩阵。其中节点i的出度数为

，就是第i行所有元素1的和，而入度数为

，就是第j列所有元素1的和，如下图：

示例-2：请以邻接矩阵表示下面有向图：

2、使用邻接表方法表示矩阵

前面介绍邻接矩阵法，优点是借着矩阵的运算，可以有许多特别的应用。要在图中加入新的边时候，这个表示法的插入与删除操作相当简易。不过要考虑到稀疏矩阵空间浪费的问题，另外如果计算所有结点的度时候，其时间复杂度为O(n的平方)

因此可以考虑更有效的方法，就是邻接表法。这种表示方法就是将一个n行的邻接矩阵，表示成n个链表，这种做法和邻接矩阵相比节省空间，如计算所有节点的度的时候，其时间复杂度为O(n+e)，缺点是有新边加入图中或从图中删除边时就要修改相关的链接，较为麻烦

（1）无向图的邻接表

（2）有向图的邻接表

邻接矩阵法和邻接表法优缺点比较总结：

（1）邻接矩阵法

优点：

【1】实现简单

【2】计算度数相当方便

【3】要在图中加入新边时，这个表示法的插入与删除操作相当容易

缺点：

【1】如果顶点与顶点间的路径差不多时，容易造成稀疏矩阵而浪费存储空间

【2】计算所有顶点的度时，其时间复杂度为O（n的平方）

（2）邻接表法

优点：

【1】和邻接矩阵相比，比较节省空间

【2】计算所有节点度数时，其时间复杂度为O（n+e），比邻接矩阵法计算快

缺点：

【1】欲求入度数时，必须先求其反转线性表

【2】新边的加入图中或从图中删除边时就要修改相关的链接，较为麻烦费时

3、邻接复合链表法

上面介绍了两个图表示法是从图的顶点出发，但如果要处理的是“边”则必须使用邻接复合链表（或称为邻接多叉链表）。邻接复合链表是处理无向图的另一种方法。邻接复合链表的节点用于存放边的数据，其结构如下：

其中相关特性说明如下：

M：是记录该边是否被找过的一个位的字段

V1和V2：是所记录的边的起点与终点

LINK1：在尚有其它顶点与 V1相连的情况下，此字段会指向下一个与V1相连的边节点，如果已经没有任何顶点与V1相连时，则指向NULL

LINK2：在尚有其它顶点与 V2相连的情况下，此字段会指向下一个与V2相连的边节点，如果已经没有任何顶点与V2相连时，则指向NULL

现在以“邻接复合链表” 来表示下面的无向图：

分别把顶点和边的节点找出，生成的邻接复合链表如下图所示：

4、索引表格法

索引表格法，是一种用一维数组来按序存储与各个顶点相邻的所有顶点，并建立索引表格来记录各个顶点在此一维数组中第一个与该顶点相邻的位置，如下图：

范例：下图为欧拉七桥问题的示意图，A、B、C、D为4个岛，1、2、3、4、5、6、7为7座桥，现在以不同的数据结构描述此图，试说明3种不同表示法

欧拉七桥是一种复线图，它并不是图论中定义的 图，必须将其分解，如下图所示：

【1】邻接矩阵

Aij = 0表示顶点i和顶点j没有相邻的边

Aij = 1表示顶点i和顶点j有相邻的边

【2】邻接表法

【3】索引表格法