第五章 图内容概述图是一种应用非常广泛的数据结构，目前已被应用于社会、化学、管理学、地理和电子工程等不同领域。例如，图常用于化合物（特别是碳氢化合物）的分子结构研究、空中航线和通信网络的描述、项目策划、遗传研究、统计等。本章将介绍：图的基本概念；邻接矩阵、邻接表等存储表示；处理图的几个重要算法，包括深度优先搜索、广度优先搜索；图的应用，包括拓扑排序、最小生成树、最短路径。重点与难点重点包括：图的邻接矩阵和邻接表存储结构，图的深度优先和广度优先遍历，最小生成树、拓扑排序、关键路径和最短路径的求解。难点包括：求最小生成树、拓扑排序、关键路径和最短路径算法。思考1图是一种相对于线性表、树更复杂的数据结构，其复杂性体现在何处？2在解决图的具体应用问题时，图的存储表示（邻接矩阵、邻接表）的选取标准是什么？3论述图的深度优先搜索遍历的策略4编写一个实现连通图G的深度优先搜索遍历的非递归程序。5论述图的广度优先搜索遍历的策略6论述Prim算法的基本思想。使用Prim算法构造如下图所示的图G的一棵最小生成树。7为什么寻找最短路径的算法称为“贪婪”算法？8论述FLOYD算法的基本思想。9有向网G2的邻接矩阵如下所示，利用FLOYD算法求出所有顶点之间的最短路径，写全过程。第一节图的教学结构图是一种相对于线性表、树更复杂的数据结构。为了更好的理解图结构，本节从图的实例入手全面分析图的定义、图的特性和图的抽象类型。1、图的定义在给出图（Graph）的定义之前，先看一个图的应用举例。例5-1航空公司需要设计一个航线咨询系统来处理乘客从某个城市飞往另一个城市的请求。问题的求解方案：用图描述航线（参见图5-1（a），对图进行穷举搜索，以确定从起始城市到目的城市之间的航线。如果乘客对航线提出进一步的要求，譬如要求航线中的中转站最少，则这个问题反映到图上就是要找一条从起点到终点所含边数最少的路径。求解方法是从起始顶点出发对图做广度优先搜索，一旦遇到目的顶点就终止。如果乘客为了节省费用需要一条飞行距离最短的航线，则问题反映在图上就是求解从起始顶点到目的顶点的最短路径，问题的求解方案则分别采取对图进行广度优先搜索和求解最短路径。给出了图的几个示例。显然，图提供了一种用图形说明数据的方法。不过，图也表示了数据项之间的关系，图的这种性质非常重要。子图由图的顶点子集和边的子集组成。图5-2给出了图5-1（b）的部分子图。如果图中的某两个顶点v和w由一条边e=（v，w）连接在一起，则称顶点v与w相邻接，v与w互为邻接点（Adjacent），而边e依附于（Incident）顶点v和w，或者说边e与v和w相关联。如果顶点对是无序的，则图G称为一个无向图；如果顶点对是有序的，则图G称为有向图。有向图的顶点对通常表示为V，w，表示从v到w的一条弧，且称v为弧尾或初始点，称w为弧头或终端点。常用术语digraph表示有向图，术语graph表示无向图。例如图5-1（a）G1是一个有向图，其中城市（A，B，G）是顶点，从一个顶点到另一个顶点的有向边（用带箭头的线段表示）则表示一条航线。图5-1（b）G2是一个无向图，图中顶点代表建筑物，无向边代表建筑物之间的道路，宿舍与图书馆是相邻接的。两个顶点之间的路径是从一个顶点开始而结束于另一个顶点的顶点序列，且每一个顶点与下一个顶点相邻接。路径的长度是指一条路径上经过的边的数目。顶点序列中顶点不重复出现的路径称为简单路径。例如图5-1（b）中，宿舍图书馆体育场是一条简单路径。起点与终点是同一个顶点的路径叫做回路或环（Cycle）。除起点与终点之外，其余顶点不重复出现的回路，称为简单回路。例如图5-1（a）中，定点序列（C，F，G，C）是一条简单回路。在无向图中，如果每一对不同的顶点之间都有一条路径，则图是连通的（Connected）。也就是说，在连通图中，从任意一个顶点出发，都可以沿一条路径到达其它顶点。图5-3（a）是一个连通图，图5-3（b）是一个非连通图。注意：连通图不一定在每对顶点之间都有一条边。如果在图中每一对不同的顶点之间都有一条边，则称之为完全（Complete）图。图5-3（c）是一个完全图的示例。显然，完全图是连通图，反之则不然。无向图G中极大连通子图称为G的连通分量。图5-4（a）是一个非连通图，但有三个连通分量。在有向图G中，如果对于每一对vi，vjV，vivj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。例如图5-1（a）中的航线图不是强连通图，但图5-5是它的一个强连通分量。一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的若干条边。图5-6是G3中最大连通分量的一棵生成树。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路。一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边，则是非连通图。如果多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。例5-2是一个生成树的应用举例。例5-2局域网LAN扩展的常规做法是利用透明网桥（Bridge）连接不同的局域网段。为了提高扩展局域网的可靠性，我们可以在LAN之间设置并行的两个或多个网桥，如图5-7所示。但是，由于在拓扑结构中产生了回路，这样配置引起了另外一些问题：由于透明网桥对于目的地址不明确的帧采取扩散算法，在本例中网桥B1、B2将目的地址不明的帧F分别复制到LAN2中形成帧F1、F2。紧接着，桥B1看见目的地不明确的帧F2，将其复制转发到LAN1，产生一个新帧，如F3（图中未画出）；类似地，桥B2也将F1复制转发到LAN1，产生F4。随后，桥B1又复制转发F4，而桥B2则复制转发F3，无限循环下去。解决这个难题的方法是让网桥相互通信，并用一棵覆盖到每个LAN的生成树（SpanningTree）覆盖实际的拓扑结构。生成树网桥是DEC公司针对透明网桥中存在的环路问题而提出的，IEEE将其标准定义802.1d。有时图的边或弧具有与它相关的数值，这种与图的边或弧相关的数值叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网（Network）。2、图的特性设G是一个无向图，顶点vi的度（Degree）di是与顶点相连的边的个数。对于图5-4中的G3，dA=4，dB=2，dC=1。特性1设G=（V，E）是一个无向图，用V表示顶点个数，用E表示边的个数。令V=n，E=e，di为顶点i的度，则有1）=2e2）0en(n-1)/2对于无向图，e的取值范围是0n（n-1）。一个具有n个顶点，n（n-1）条边的无向图是一个完全图。设G是一个有向图，顶点vi的入度（In-Degree）d是以顶点vi为头的弧的数目。顶点vi的出度（Out-Degree）d是以顶点vi为尾的弧的数目。例如，对于图5-1（a），d=2，d=0。对于有向图，一个顶点的度是该顶点的入度与出度之和。特性2设G=（V，E）是一个有向图，n和e的含义与特性1相同，则1）=e2）0en(n-1)对于一个有向图，e的取值范围是0n（n-1）。一个具有n个顶点，n（n-1）条边的有向图是一个完全图。3、图的抽象类型图是一种数据结构，加上一组基本操作，就构成了抽象数据类型。抽象数据类型Graph专指无向图，而抽象数据类型Digraph专指有向图。图的抽象数据类型定义如下：ADTGraph/Digraph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR对于有向图VR=V，w|v，wV且P(v，w),V，w表示从v到w的弧，谓词P(v，w)定义了弧V，w的意义或信息对于无向图VR=(v，w)|v，wV且P(v，w),(v，w)表示从v到w的边，谓词P(v，w)定义了边(v，w)的意义或信息基本操作P：CreateGraph（G，V，VR）返回结果：V是图的顶点集，VR是图中边或弧集合。按V和VR的定义构造图G。DestoryGraph（G）初始条件：G是已经存在的一个图。操作结果：销毁图G。Exist（G，v，w）初始条件：G是已经存在的一个图，v、w是两个顶点。操作结果：如果存在边（v，w）或弧V，w，则返回TRUE，否则返回FALSE。Edges（G）初始条件：G是已经存在的一个图。操作结果：返回图中边的数目。Vertices（G）初始条件：G是已经存在的一个图。操作结果：返回图中顶点的数目。Add（G，v，w）初始条件：图G已存在，v，w是两个顶点。操作结果：如果G是有向图，则在G中添加一条弧V，w；如果G是无向图，则在G中添加一条边（v，w）。Delete（G，v，w）初始条件：图G已存在，v，w是两个顶点。操作结果：如果G是有向图，则在G中删除一条弧V，w；如果G是无向图，则在G中删除一条边（v，w）。Degree（G，v）初始条件：图G及顶点v已存在。操作结果：返回图G中顶点v的度。Indegree（G，v）初始条件：图G及顶点v已存在。操作结果：如果G是有向图，则返回顶点v的入度；如果G是无向图，则返回图G中顶点v的度。Outdegree（G，v）初始条件：图G及顶点v已存在。操作结果：如果G是有向图，则返回顶点v的出度；如果G是无向图，则返回图G中顶点v的度。DFSTraverse（G，v，visit（）初始条件：图G已存在，v是G中的某个顶点，visit是顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，并对顶点调用函数visit一次且仅一次。一旦visit失败，则操作失败。BFSTraverse（G，v，visit（）初始条件：图G已存在，v是G中的某个顶点，visit是顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，并对顶点调用函数visit一次且仅一次。一旦visit失败，则操作失败。ADTGraph/Digraph第二节图的计算机表示如果编写程序解决关于图的问题，则首先必须找到表示图的抽象数据类型的方法。通常不直接表示边（或弧）的集合，而是根据它们与每个独立顶点的依附关系来表示。无向图和有向图最常用的描述方法都基于邻接的方式：邻接矩阵、邻接链表。1、邻接矩阵表示法一个n个顶点的图G=（V，E）的邻接