图（graph） 原

图（graph）

图是非线性数据结构，是一种较线性结构和树结构更为复杂的数据结构，在图结构中数据元素之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

1、概念

1．定义

图（graph）是一种网状数据结构，图是由非空的顶点集合和一个描述顶点之间关系的集合组成。

二元组定义：G=(V,E)

• V：表示元素的非空有限集合。元素通常称为顶点（Vertex）。
• E：表示元素之间关系的有限集集合。

如果图的边限定为从一个顶点指向另一个顶点，即每条边都是顶点的有序偶对，称之为有向图（directed graph）。

方向起始的顶点称为起点或尾（弧尾）。方向指向的顶点称为终点或头（弧头）。

如果图中的边没有方向性，即每条边都是顶点的无序偶对，称之为无向图（undirected graph）。

设图G=(V,E)和图G'=(V',E')。如果V’⊆V且E’⊆E，则称G'是G的一个子图（subgraph）。 如果V’=V且E’⊆E，则称G’是G的一个生成子图（spanning subgraph）。

有n(n-1)/2条边的无向图称为无向完全图。

有n(n-1)条边的有向图称为有向完全图。

有很少边的图称为稀疏图。

边较多的图称为稠密图。

2．基本术语

对于无向图G=(V,E)，如果边(u,v)∈E，则称顶点u与顶点v互为邻接点。

两个邻接点连成的边叫做两个节点的相关边。

与每个顶点相连的边的数叫该点的度（degree）。

对有向图中某结点的弧头数称为该结点的入度（in degree）。

对有向图中某结点的弧尾数称为该结点的出度（out degree）。

有度=入度+出度

在一个图中，某个顶点Vp出发，沿着一些边经过一些顶点，到达Vg则称经过的这些顶点序列为Vp到Vg的路径。Vp是路径的始点，Vg是路径的终点。

对于有向图路径也是有向的，路径的方向只能是从起点到终点，且与它经过的每一条边的方向一致。

路径上的边或弧的数目称之为该路径的长度。

除始点和终点外，其他各顶点均不同的路径称之为简单路径。

从一个顶点出发又回到该顶点，则所经过的路径称为回路。

始点和终点相同的简单路径称之为简单回路。

在无向图中，从一个顶点到另一个顶点之间有路径，则称这两个顶点是连通的。

如果图中任意一对顶点之间都是连通的，则称此图为连通图。

非连通图中的每一个连通部分叫连通分量。

对于有向图，若两点之间有互相到达的路径，则称这两点是强连通。

如果有向图中任何一对顶点都是强连通的，则此图叫强连通图。

有向图中最大连通子图称为有向图的强连通分量。

有些图对应每条边有一相应的数值，这个数值称为该边的权。

带权的图称为网（network）。网可分为有向网和无向网。

3．ADT定义

如下是图的抽象数据类型定义：

ADT Graph{
数据对象D：D是具有相同性质的数据元素的集合。
数据关系R：R={<u,v>|P(u,v)∧(u,v∈D)}
基本操作：
getType();				//返回图的类型
getVexNum();			//返回图中顶点数
getEdgeNum();			//返回图中边数
getVertex();				//返回图中所有顶点的迭代器
getEdge();				//返回图中所有边的迭代器
remove(v);				//在图中删除特定的顶点
remove(e);				//在图中删除特定的边
insert(v);				//在图的顶点集中添加一个新顶点
insert(e);				//在图的边集中添加一条新边
areAdjacent(u,v);		//判断v是否是u的邻接点
edgeFromTo(u,v);		//返回u到v的边，如果不存在返回空
adjVertexs(u);			//返回顶点u的所有邻接点
DFSTraverse(v);			//从顶点v开始深度优先搜索遍历图
BFSTraverse(v);			//从顶点v开始广度优先搜索遍历图
shortestPath(v);			//求顶点v到图中所有顶点的最短路径
generateMST();			//求无向图的最小生成树，有向图不支持此操作
toplogicalSort();		//求有向图的拓扑序列。无向图不支持此操作
criticalPath();			//求有向无环图的关键路径。无向图不支持此操作
}ADT Graph

2、存储结构

从图的逻辑结构定义来看，无法将图中的顶点排列成一个唯一的线性序列。在图中任意一个顶点都可以看成是图的第一个顶点，对任何一个顶点而言，它的邻接点之间也不存在顺序关系。为了方便存储和操作，需要将图中的顶点按一定的序列排列起来。

顶点在图中的位置就是指该顶点在人为确定的序列中的位置。

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区的位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组来表示数据元素之间的关系。

借助数组存储的方法有邻接矩阵表示法和邻接表表示法。

1．邻接矩阵表示法

1>定义

图的邻接矩阵（adjacent matrix）表示法是使用数组来存储图结构的方法，也被称为数组表示法。 它采用两个数组来表示图：一个是用于存储所有顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组也被称为邻接矩阵。

2>性质

邻接矩阵有如下特性：

• （1）图中各顶点序号确定后，图的邻接矩阵是唯一确定的。
• （2）无向图和无向网的琳姐矩阵是一个对称矩阵。
• （3）无向图邻接矩阵中第i行或第i列的非0元素个数即为第i个顶点的度。
• （4）有向图邻接矩阵第i行非0元素个数为第i个顶点的出度，第i列非0元素个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非0元素个数之和。
• （5）无向图的边数等于邻接矩阵中非0元素个数之和的一半，有向图的弧数等于邻接矩阵中非0元素个数之和。

3>优缺点

优点：

邻接矩阵表示法对于以图的顶点为主的运算比较适合。

缺点：

除完全图外，其他图的邻接矩阵有许多零元素，特别是当n值较大，而边数相对完全图的边n-1又少的多时，则此矩阵称为稀疏矩阵，非常浪费存储空间。

2．邻接表表示法

邻接表（adjacency list）是图的一种链式存储方法，邻接表表示法类似于树的孩子链表表示法。

在邻接表中对于图G中的每个顶点vi建立一个单链表，将所有邻接于vi的顶点vj链成一个单链表，并在表头附设一个表头结点，这个单链表就称为顶点vi的邻接表。

1>结点

邻接表中共有两种结点结构，分别是边表结点和表头结点。

邻接表中的每一个结点均包含有两个域：邻接点域和指针域。

• 邻接点域用于存放与定点vi相邻接的一个顶点的序号。
• 指针域用于指向下一个边表结点。

边表结点由3个域组成：

• 邻接点域（adjvex）指示与定点vi邻接的顶点在图中的位置。
• 链域（nextdge）指向下一条边所在的结点。
• 数据域（info）存储和边有关的信息。

头结点由2个域组成：

• 链域（firstedge）指向链表中的第一个结点之外。
• 数据域（data）存储顶点相关信息。

如下图为邻接表的存储示例：

2>分类

在无向图的邻接表中，顶点的每一个边表结点对应于与顶点相关联的一条边。

在有向图的邻接表中，顶点的每一个边表结点对应于以顶点为始点的一条弧，因此也称有向图的邻接表的边表为出边表。

在有向图的邻接表中，将顶点的每个边表结点对应于以顶点为重点的一条弧，即用便捷点的邻接点域存储邻接到顶点的序号，由此构成的邻接表称为有向图的逆邻接表，逆邻接表有边表称为入边表。

3>邻接表与邻接矩阵的关系

邻接表与邻接矩阵的关系如下：

• （1）对应于邻接矩阵的每一行有一个线形连接表；
• （2）链接表的表头对应着邻接矩阵该行的顶点；
• （3）链接表中的每个结点对应着邻接矩阵中该行的一个非零元素；
• （4）对于无向图，一个非零元素表示与该行顶点相邻接的另一个顶点；
• （5）对于有向图，非零元素则表示以该行顶点为起点的一条边的终点。

邻接表表示法示例如下：

4>邻接表的性质

邻接表的性质如下：

• （1）图的邻接表表示不是惟一的，它与表结点的链入次序有关。
• （2）无向图的邻接表中第i个边表的结点个数即为第i个顶点的度。
• （3）有向图的邻接表中第i个出边表的结点个数即为第i个结点的出度，有向图的逆邻接表中第i个入边表的结点个数即为第i个结点的入度。
• （4）无向图的边数等于邻接表中边表结点数的一半，有向图的弧数等于邻接表（逆邻接表）中出边表结点（入边表结点）的数目。

需要说明的是：

• （1）在邻接表的每个线性链接表中各结点的顺序是任意的。
• （2）邻接表中的各个线性链接表不说明他们顶点之间的邻接关系。
• （3）对于无向图，某顶点的度数=该顶点对应的线性链表的结点数。
• （4）对于有向图，某顶点的“出度”数=该顶点对应的线性链表的结点数；求某顶点的“入度”需要对整个邻接表的各链接扫描一遍，看有多少与该顶点相同的结点，相同结点数之和即为“入度”值。

3．关联矩阵

图的另一种矩阵表示法为以顶点和边的关联关系为基础建立矩阵，这个矩阵称之为关联矩阵。定义如下：

• 图G=(V,E)的关联矩阵是一个|V|×|E|矩阵，使得：

在一个多图的关联矩阵中，一些列是相同的，一个列只有一个1则代表一个环。 如下是关联矩阵的表示：

3、图的遍历

从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这一过程称之为图的遍历。

图的遍历是图的运算中最重要的运算，图的许多运算均以遍历为基础。

图的遍历按搜索路径不同分为深度优先搜索遍历（Depth First Search）和广度优先搜索遍历（Breadth First Search）。

1．深度优先搜索遍历

深度优先搜索的基本方法是：

从图中某个顶点发v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

如下图：

图的深度优先搜索遍历是一个递归过程，其特点是尽可能先对纵深方向的顶点进行访问。

对图进行深度优先搜索遍历时，按访问顶点的先后次序所得到的顶点序列称为该图的深度优先搜索遍历序列，简称为DFS序列。

一个图的DFS序列不一定惟一，这与算法、图的存储结构以及初始出发点有关。

图的深度优先搜索算法也可以使用堆栈以非递归的形式实现，使用堆栈实现深度优先搜索的思想如下：

• ⑴首先将初始顶点v入栈；
• ⑵当堆栈不为空时，重复以下处理：
  • 栈顶元素出栈，若未访问，
  • 则访问之并设置访问标志，将其未曾访问的邻接点入栈；
• ⑶如果图中还有未曾访问的邻接点，选择一个重复以上过程。

2．广度优先搜索遍历

广度优先搜索遍历的基本方法是：

假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”先被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

过程如下图：

图的广度优先搜索遍历是一个递归过程，其特点是尽可能先对横向的顶点进行访问。

对图进行广度优先搜索遍历时，按访问顶点的先后次序所得到的顶点序列，称为该图的广度优先搜索遍历序列，简称为BFS序列。

一个图的BFS序列不一定惟一，这与算法、图的存储结构以及初始出发点有关。

广度优先搜索遍历的实现与树的按层遍历实现一样都需要使用队列，使用队列实现广度优先搜索的思想如下：

• ①首先访问初始顶点v并入队；
• ②当队列不为空时，重复以下处理：
  • 队首元素出队，访问其所有未曾访问的邻接点，并它们入队；
• ③如果图中还有未曾访问的邻接点，选择一个重复以上过程。

4、最小生成树

图论中，通常将树定义为一个无回路连通图。对于无回路连通图，只要选定某个顶点作为根，以此顶点为树根对每条边定向，竟能得到通常的树。

1．生成树

一个连通图G的子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。

生成树有一下特点：

• （1）如果在生成树中去掉任何一条边，此子图就会变成非连通图。
• （2）任意两个顶点之间有且仅有一条路径，如再增加一条边就会出现一条回路。
• （3）有遍历连通图G时，所经过的边和顶点构成的子图是G的生成树。

由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树。

由广度优先搜索得到的生成树称为广度优先生成树，简称为BFS生成树。

由图的遍历可得如下概念：

若从图的某个顶点出发，可以系统地遍历图中的所有顶点，则遍历时，经过的边和图的所有顶点所构成的子图，称为图的生成树。

2．最小生成树的生成

对于连通网络G=(V,E)，边是带权的，因而G的生成树的各边也是带权的。生成树的各边的权值总和称为生成树的权，并把权最小的生成树称为G的最小生成树。

构成最小生成树的方法有多种。这些算法可以分为下面几类：

• （1）创建并扩展一些树，使它们合并成更大的树。
• （2）扩展一个数的集构成一棵生成树，如：Kruskal算法。
• （3）创建并扩展一棵树，为它添加新的树枝。如Prim算法。
• （4）创建并扩展一棵树，为它添加新的树枝，也可能从中删除一些树枝。

3．MST性质

无论上述那种类型的算法，均用到了最小生成树的如下性质。

设G=(V,E)是一个连通网络，U是顶点集V的一个真子集。如果(u,v)是G中所有的一个端点在U（即u∈U）里，另一个端点不在U（即v∈V-U）里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边（u,v）。这个性质称为MST性质。

4．Prim（普里姆）算法

设G(V,E)为一个连通网，顶点集V=(v1,v2,……,vn)。设T(U,TE)是所要求的G的一棵最小生成树，其中U是T的顶点集，TE是T的边集，并且将G中边上的权看作是长度。

普里姆算法的基本思想：

首先任选V中一个顶点v1，构成入选顶点集U={v1}，此时入选边集TE为空集，V中剩余顶点构成待选顶点集V-U；在所有关联于入选顶点集和待选顶点集的边中选取权值最小的一条边（vi,vj）加入入选边集（这里vi为入选顶点，vj为待选顶点），同时将vj加入入选定点集。重复以上过程，直至入选顶点集U包含所有顶点（U=V），入选边集包含n-1条边，MST性质保证上述过程求得的T(U,TE)是G的一棵最小生成树。

过程如下图：

5．Kruskal（克鲁斯卡尔）算法

设G=(V,E)是连通网络，令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,Φ)，T中的每个顶点自成一格连通分量。按照长度递增的顺序依次选择E中的边（u,v），如果该边断点u、v分别是当前T的两个连通分量T1、T2中的顶点，则将该边加入到T中，T1、T2也由此边连接成一格连通分量；如果u、v是当前同一个连通分量中的顶点，则舍去此边，这是因为每个连通分量都是一棵树，此边添加到树中将形成回路。依次类推，知道T中所有顶点都在同一连通分量上为止。从而得到G的一棵最小生成树T。

过程如下：

克鲁斯卡尔算法和普里姆算法产生的生成树是相同的。

不同之处：

• （1）边加入树的顺序不同。
• （2）普里姆算法总是保持构造中的树是一片的，因此普里姆算法应用的整个阶段中它都是一棵树。
• （3）克鲁斯卡尔算法在执行过程中不能保持是一棵树，可能至多是树的集合。
• （4）克鲁斯卡尔算法中每条边只需考虑一次。因此克鲁斯卡尔算法更快。

5、最短路径

在许多应用领域，带权图都被用来描述某个网络，比如通信网络、交通网络等。这种情况下，各边的权重就对应于两点之间通信的成本或交通费用。此时，一类典型的问题就是：在任意指定的两点之间如果存在通路，那么最小的消耗是多少。这类问题实际上就是带权图中两点之间最短路径的问题。

在图中两点之间的最短路径问题包括两个方面：一是求图中一个顶点到其他顶点的最短路径，二是求图中每对顶点之间的最短路径。

这里的路径不是指路径上边数的总和，而是指路径上各边的权值总和。

1．单源最短路径

单源最短路径是指，在带权图G=(V,E)中，已知源点为s∈V，求s到其余各顶点的最短路径。

1>定理

若π=(u0=s,u1,u2,… ,uk=v)是从顶点s到顶点v的最短路径，则对于任何0 ≤ i < j ≤ k，τ=(ui, ui+1, … , uj)是从顶点ui到uj的最短路径。

此定理也可以简单的描述为：最短路径的子路径也是最短路径。

2>Dijkstra（迪卡斯特拉）算法

算法基本思想：

设置两个顶点集S和T，S中存放已确定最短路径的顶点，T中窜访待确定最短路径的顶点。初始时，S中仅有一个源点，T中包含除源点外其余顶点，此时各顶点的当前最短路径长度为源点到该顶点的弧上的权值。接着选取T中当前最短路径长度最小的一个顶点v加入S，然后修改T中生于顶点的当前最短路径长度。

修改原则是：当v的最短路径长度是v到T中的顶点之间的权值之和小于该顶点的当前最短路径长度时，用前者替换后者。重复上述过程，直至S中包含所有的顶点。

2．任意顶点间的最短路径

Dijkstra算法只能求出源点到其余顶点的最短路径，如果需要求出带权图中任意一对顶

点之间的最短路径，可以用每一个顶点作为源点，重复调用Dijkstra算法|V|次，时间复杂度为O(|V|^3)。

1>Floyd算法

假设求出的每对顶点之间的最短距离使用一个|V|×|V|矩阵D保存和输出。下面定义符号D(k)，0 ≤k ≤|V|。在定义中假设带权图中所有的顶点排成一个序列。

定义：D(k)（0 ≤k ≤|V|）是一个|V|阶方阵，其中D(k)[i][j]是在考虑带权图中前k个顶点，将它们作为中间顶点时从顶点vi到顶点vj的当前最短距离（1 ≤i ≤|V|，1 ≤j ≤|V|）。

D(0)表示当顶点vi，vj之间不考虑任何顶点作为中间顶点时的最短距离，显然D(0)[i][j]就是顶点vi到vj的边的权值，如果使用邻接矩阵A作为存储结构，D(0)[i][j]=A[i][j].weight。并且如果将所有的顶点均考虑在内，vi到vj的当前最短距离就是在图中vi到vj的最短距离，即δ(vi,vj) = D(|V|)[i][j] （1 ≤i ≤|V|，1 ≤j ≤|V|）。

Floyd算法的基本思想是：

• (1)用邻接矩阵初始化D(0)，对角线元素为0；
• (2)在顶点vi、vj之间考虑顶点v1，比较在引入v1之后vi到vj的当前最短距离是否可以通过v1变得更小。把v1放在vi到vj的路径上，vi到vj之间可能会产生新的路径，其距离为D(0)[i][1] + D(0)[1][j]，当然v1的引入可能反而会加大vi到vj的距离，因此需要比较D(0)[i][1] + D(0)[1][j]与D(0)[i][j]的大小。最终，在考虑v1之后vi到vj的当前最短距离为两者中小的。即： D(1)[i][j] = min{ D(0)[i][1] + D(0)[1][j] , D(0)[i][j]}
• (3)一般情况下，如果在考虑了前k-1个顶点{v1, v2, … , vk-1}之后，从顶点vi到vj的当前最短距离是D(k-1)[i][j]。那么在顶点vi、vj之间考虑前k个顶点时，顶点vi到vj的当前最短距离为以下两个距离中小的：在考虑前k-1个顶点基础上将vk放在vi到vj的路径上，此时产生新的路径长度为D(k-1)[i][k] + D(k-1)[k][j]；以及不将vk放在vi到vj的路径上的距离D(k-1)[i][j]。最终，在考虑前k个顶点{v1, v2, … , vk}之后，vi到vj的当前最短距离 D(k)[i][j] = min{ D(k-1)[i][k] + D(k-1)[k][j] , D(k-1)[i][j]} 1 ≤k ≤|V|
• (4)依次进行下去，直到k = |V|。此时D(|V|)[i][j]即为带权图中任意两个顶点vi到vj的最短距离。

6、拓扑排序

有向无环图（directed acyclic graph）是指一个无环的有向图，简称DAG。

用顶点表示活动（Activity），用弧表示活动之间的先后次序关系的有向图，称为顶点活动图（Activity On Vertex Network），简称为AOV网。

AOV网的特点是在网中一定不能有有向回路。检测网中是否存在环，则采用拓扑排序的方法。

1．概念

在一个AOV网络中，若vi为vj的先行活动，vj为vk的先行活动，则vi必为vk的先行活动，即活动的先行关系具有传递性。

如果从离散数学的观点看AOV网络中的活动关系可以看成是一个偏序关系，工程完成活动的线性序列可以看成是一个全序关系。

由某个集合上的一个偏序得到该集合上的一个全序，此操作称之为拓扑排序（topological sort）。即将AOV网络各个顶点（代表各个活动）排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。拓扑排序就是构造AOV网络顶点的拓扑有序序列的运算。

2．拓扑排序算法

拓扑排序算法的基本步骤是：

• （1）从网中选择一个入度为0的顶点并输出；
• （2）从网中删除此顶点及所有出边。
• （3）重复上述两个步骤，将删除的顶点依次排序。

3．关键路径

与AOV网络对应的是边表示活动的AOE网络。如果在有向无环的带权图中：

• 用有向边表示一个工程中的各项活动(activity)；
• 用边上的权值表示活动的持续时间(duration)；
• 用顶点表示事件(event)；
• 则这样的有向图叫做用边表示活动的网络，简称AOE (activity on edges)网络。

由于一个工程只有一个开始点和一个完成点，所以在正常情况下，AOE网络中只有一个入度为0的顶点，也只有一个出度为0的顶点，它们分别称之为源点和汇点。

在AOE网络中，有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径（critical path）

求关键路径的算法：

• ⑴对图中的顶点进行拓扑排序，求出拓扑序列与逆拓扑序列；若拓扑序列中顶点数少于|V|，说明图中有环，返回；
• ⑵Ve[ 0 ] = 0，在拓扑序列上求各顶点最早开始时间；
• ⑶Vl[n-1] = Ve[n-1]，在逆拓扑序列上求各顶点最迟开始时间；
• ⑷遍历图中所有边< u,v >∈E，判断其是否为关键活动。