假期连载之十四
(图—图的遍历、应用)
图是我们在简单数据结构部分中讨论的最后一篇，其重点主要包括离散数学中关于图论的一些理论介绍，各种性质图的存储表示优缺点分析，图的遍历算法以及部分基于遍历算法的一些实际应用问题等。可以说在图之前，数据结构所利用到的一些简单算法依然属于“入门级”，而从图开始，就要建立在较为复杂的算法分析基础上进行算法设计了。
但今后当我们接触到高级数据结构部分的内容时，恐怕又会对图这一部分稍带不屑了。
图的遍历
图的遍历从大的方向来看与树形结构类似，分深度优先和广度优先两种类型。但图有其极其特殊的一面，使它和树的算法设计上有着根本区别。
一是图不同于树的一对多的关系，而是多对多的关系，在这些关系中可能是非连通图，也有可能含有回路存在。这有点类似于我们曾提到的迷宫解法，但事实上用图来解迷宫问题有点杀鸡用牛刀的感觉，且在一些情况中甚至还无法用图来构建。
总之图的遍历一般情况下需要回溯，为了防止重复访问结点，需要额外设置一个访问标志数组visited[n]，用于记录已访问过的结点。
1、 深度优先搜索
图的深度优先搜索是从树的先根遍历算法推广而来的，其原则是按深度方向搜索。其算法思想是：
1） 从图中某个顶点v0出发，首先访问v0；
2） 找出刚访问过的顶点的第一个未被访问的邻接点，然后访问该结点。以该结点为新结点，重复此步骤，直到刚访问过的顶点没有未被访问的邻接点为止；
3） 返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点，然后执行步骤2。
我们用深度优先顺序模拟遍历图，在算法前进的方向所连成的结点序列构成以A为根的树，称为深度优先搜索树。
下面给出C语言描述的深度优先搜索—邻接矩阵法表示。
void DepthFirstSearch(AdjMatrix g,int v0)
{
visit(v0);
visited[v0]=True;
for(vj=0;vj<g.vexnum;vj++)
if(!visited[vj]&&g.arcs[v0][vj].adj==1)
DepthFirstSearch(g,vj);
}//如果读者有兴趣，可以自己写出工作栈条件下的非递归算法，两种同样重要
2、 广度优先搜索
广度优先搜索即是从树和森林的广度优先遍历算法推广而来的。其算法的基本思想是：
1）从图中某个顶点v0出发，首先访问v0；
2）依次访问v0的各个未被访问的邻接点；
3）分别从这些邻接点出发，依次访问它们的各个未被访问的邻接点。在访问时应保证以下规则：如果vi和vk为当前端接点，且vi在vk之前被访问，则vi的所有未被访问的邻接点应在vk的所有未被访问的邻接点之前被访问。
由于广度优先搜索实质上是按层次顺序搜索，因此算法不涉及回溯，借鉴树的经验，我们依然采用队列一次存储一层结点的方式组织算法，便于确保访问该层所有结点。
图的应用
图的应用是广泛且复杂的。在介绍其具体应用之前，需要了解几个关于图应用的几个前置概念。
1、连通分量
当无向图为非连通图时，从图中某一个顶点出发，利用深度或广度优先搜索算法无法遍历所有顶点，而只能访问到该结点所在的最大连通子图中的所有顶点，这些顶点构成一个连通分量connected component。在这种情况下，对图的遍历应以连通分量为单位进行，才能确保遍历全部顶点。
以此作为推广，在无向连通图中，顶点v被称为关节点articulation point，当且仅当删去v及依附于v的所有边之后，G被分割为至少两个连通分量。我们把没有关节点的图称为重连通图biconnected graph。
2、简单路径
简单路径是指图中顶点u到顶点v的一条路径中，其顶点均不相同的路径。通过简单分析可知，两顶点间可能存在多条简单路径，我们可以对遍历算法进行适当改进，使求得的解为简单路径。
3、生成树
一个连通图的生成树是指一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。如果在生成树上添加一条边，则必然形成一个环。一个有n个顶点的生成树仅有n-1条边，如果多余n-1则必然有回路，但是含有n-1条边的土并非是连通图，就不一定存在生成树，如果一个图的边数少于n-1，则其必然是非连通图。
在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树Minimum Cost Spanning Tree，简称为最小生成树MST。
最小生成树具有一条重要性质：设N={V,{E}}是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U，v属于V-U，则存在一棵包含边(u,v)的最小生成树。
利用MST的上述性质，我们可以生成一个连通网的最小生成树。其中Kruskal算法和Prim算法是最为经典的。
1）Kruskal
假设N=(V,{E})是连通网，将N中的边按权值从小到大的顺序排列。
a）将n个结点看成n个集合；
b）按权值从小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中，同时将该边的两个顶点所在的顶点集合合并。
c）重复b直到所有的顶点都在同一个顶点集合内。
2）Prim
假设N=(V,{E})是连通网，TE为最小生成树中边的集合。
a）初始U={u0|u0属于V，TE为空}；
b）在所有u属于U，v属于V-U的边种选择一条代价最小的边（u0,v0）并入集合TE，同时将v0并入U。
c）重复b直到U=V为止，此时TE中必含有n-1条边，则T=( V,{TE})为N的最小生成树。
4、拓扑排序
有向无环图Directed Acyclic Graph是指一个无环的有向图，简称DAG。我们一般用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网Activity On Vertex Network，简称AOV-网。
在有向图G=(V,{E})中，V中顶点的线性序列（v1,v2,…,vn）称为拓扑序列。如果此序列中任意两个顶点vi、vj，在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。
现已知AOV-网的特性如下：
1、 AOV-网中不能存在回路，否则回路中的活动就会互为前驱，从而无法执行。
2、 AOV-网的拓扑序列是不唯一的。
为求有向无环图的拓扑序列，就是拓扑排序问题Topological Sort。其基本思想为：
1、 从有向图中选一个无前驱的结点数出。
2、 将此结点和以它为起点的弧删除。
3、 重复1、2，直到不存在无前驱的结点。
4、 若此时输出的结点数小于有向图中的结点数，则说明有向图存在回路，否则输出的顶点顺序即为一个拓扑序列。
5、 关键路径
有向图通常被用来表示工程计划时有两种方法：
1、 用顶点表示活动，即AOV-网；
2、 用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。
把第二种方法构造的有向无环图称为边表示活动的网Activity On Edge Network。简称AOE-网。
AOE-网中存在唯一的、入度为0的顶点，叫做源点。存在唯一的，出度为0的点，叫做汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需要的时间，该路径叫做关键路径，关键路径上的活动称为关键活动。
求关键路径的基本步骤如下：
1、 对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)。
2、 按逆拓扑序列求每个事件的最晚发生时间vl(i)。
3、 求出每个活动ai的最早开始时间e(i)和最晚发生时间l(i)。
4、 找出e(i)=l(i)的活动ai，即为关键活动。
6、 最短路径问题
所谓最短路径Shortest Path问题是指：从在带权图的某一个顶点（称为源点）出发，找出一条通往另一顶点（称为终点）的最短路径。所谓“最短”，也就是沿路径各边的权值达到最小。
最短路径问题分为以下三种情况表示：
1、 非负权值的单源最短路径
求此类型的最短路径，经典算法是由计算机大拿Dijkstra提出的按路径长度的递增次序确定最短路径的Dijkstra算法。
2、 任意权值的单源最短路径
假设有向带权图某条边的长度为负，那么根据Dijkstra算法，结果并不正确。为了求解这种情况下的最短路径问题，Bellman和Ford提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度算法。该方法有一个限制条件，即有向图中不能包含带有负值边的回路。
3、 所有顶点之间的最短路径
对于一个各边权值均大于0的有向带权图，求出所有顶点之间的最短路径和最短路径长度，一个办法是轮流以每个顶点为源点，重复执行Dijkstra算法n次，就可求得每一对顶点之间的最短路径和最短路径长度。
为了使算法结构更为清晰，Floyd算法实现了这一要求，尽管其时间复杂度上与前者相当。
Floyd算法使用图的邻接矩阵Edge[n][n]来表示有向带权图。算法的基本思想是，设置一个n阶方阵A，其中除对角线的矩阵元素为0外，其他元素a[i][j]表示从点vi到vj的有向路径长度。在vi、vj间插入v0、v1、…直到n-1次，每步比较前者和后者的长度，并取较短的路径作为中间顶点号不大于0的最短路径。最终得到的必是vi和vj的最短路径。事实证明Floyd算法在逻辑上更符合题设的要求。
在今后的连载中，我们会特别针对图的六个核心应用问题进行专题讨论，并且陆续放出相关算法的最终代码。
至此，简单数据结构部分的内容就全部讨论完毕。这些结构都是被经常用在各种程序设计当中，并被作为程序设计的核心问题之一。
接下来的连载，除了开辟必要的两篇来丰富和总结前面的不足之外，我们会进入简单算法设计部分的讨论，这些算法都是基于上述十四篇连载的内容而来，使数据结构的实际应用更加深入了一步。
（未完待续）