《数据结构（C#）》-第7章 图

第7章

图7.1基本定义和术语

7.2图的存储结构

7.3图的遍历

7.4最小生成树

7.5最短路径7.6拓扑排序

图（Graph）是一种较为复杂的数据结构，是一种图状结构，比线性表和数更为复杂的数据结构。在图中，任何结点都可以相互建立联系，可以任意连接，图中的任意两个结点之间都有可能相关。近年来信息社会飞速发展，图的应用更为广泛，已渗透到逻辑学、物理、化学、语言学、计算机科学、人文科学和自然科学中，以及数学中。7.1基本定义和术语图(Graph)是由非空的顶点(Vertices)集合和描述顶点之间的关系——边（Edge）或弧（Arc）的集合组成。其形式化定义为：G＝（V，E）V＝{Vi|Vi∈dataobject}E＝{(Vi，Vj)|Vi,Vj∈V∧P(Vi,Vj)}图的定义（1）无向图（2）有向图（3）顶点、边、弧、弧头、弧尾（4）无向完全图、有向完全图（5）顶点的度、入度、出度（6）边的权、网图（7）路径、路径长度（8）简单路径、回路、简单回路（9）子图（10）连通图、连通分量（11）强连通图、强连通分量（12）生成树（13）生成森林图的相关术语图的基本操作图和其他的数据结构一样，它的基本操作包括查找、插入和删除。图的基本操作说明：

1）GetNumOfVertex()如果图存在；则返回图中的顶点数。

2）GetNumOfEdge()如果图存在；则返回图中的边或弧的数目。

基本定义和术语3）SetEdge(Node<T>V1,Node<T>V2,intv)如果图存在，顶点V1和V2是图的两个顶点；那么在顶点V1和V2之间添加一条边或弧并设边或弧的值为v。

4）DelEdge(Node<T>V1,Node<T>V2)如果图存在，顶点V1和V2是图的两个顶点并且V1和V2之间有一条边或弧；则删除顶点V1和V2之间的边或弧。

5）IsEdge(Node<T>V1,Node<T>V2)如果图存在，顶点V1和V2是图的两个顶点；如果V1和V2之间有一条边或弧，返回true,否则返回false。基本定义和术语例：在无向图G1和有向图G2中找出各个顶点的入度和出度。基本定义和术语例:如下图所示无向网图，查看各条边的特点和权值。7.2图的存储结构

图的结构很复杂，任意两个顶点之间都有可能存在联系，所以没有办法用数据元素在存储区中的物理位置来表示元素与元素之间的关系，但是，可以借助元素与元素相邻接的关系来表示元素之间的关系。下面将介绍两种常用的表示方法，对无向图和有向图都有效，它们是邻接矩阵和邻接表表示法。邻接矩阵邻接矩阵（AdjacencyMatrix）很容易判断任意两个顶点之间是否有边或弧相连接，并且容易得出图中各个顶点的度。设图G＝(V，E)是具有n个顶点，图的邻接矩阵是n阶方阵A，若G是无向图，其中的元素表示为：若G是网络，则邻接矩阵可定义为：例：无向图G7和有向图G8的邻接矩阵分别为A1和A2，用邻接矩阵表表示。

无向图G7和有向图G8邻接表

邻接表（AdjacencyList）是图的一种链式存储结构。在邻接表中，图的各个顶点也是顺序存放的。在邻接表中，我们为每个顶点建立一个单链表结点，把所有邻接于某个顶点的顶点构成一个表，采用链式存储结构。每个单链表由邻接顶点域adjvex和引用域next表示，邻接顶点域用来存放邻接顶点的信息，即邻接顶点在顶点数组中的序号；引用域用来存放下一个邻接点的地址。例：用邻接表表示无向图G7和有向图G8。邻接表算法无向图邻接表的存储结构可用无向图邻接表类来表示，类中主要存储的是邻接表结点。邻接表结点用类adjListNode<T>来描述，类中有两个成员，一个是存储邻接顶点adjvex的信息，一个是存储下一个邻接表节点next的地址，类的实现见教材。}无向图邻接表中顶点节点类用VexNode<T>表示，它包括两个成员字段，一个是用来存储图中顶点本身的信息data，一个用来存储顶点的邻接表中第一个结点的地址firstAdj。VexNode<T>的实现见教材。7.2图的存储结构无向图邻接表中包括顶点结点和邻接表结点，把这些结点组合到一起，我们还需要定义一个无向图邻接表类GraphAdjList<T>，该类中有一个成员字段用来表示邻接表数组adjList。GraphAdjList<T>类继承了接口IGraph<T>，并实现了其中的方法，两个方法成员是IsNode和GetIndex。功能与GraphMatrix<T>一样。无向图邻接表类GraphAdjList<T>的实现见教材。在无向图邻接表类中，有几个方法需要说明一下：1）GetNumOfVertex()方法算法思路：要求无向图的顶点数量，直接返回adjList数组的长度即可。2）GetNumOfEdge()方法

算法思路：要求无向图的边数，需要求出所有顶点的邻接表的结点的个数，然后除以2。

3）SetEdge(Node<T>V1,Node<T>V2,intV)方法

算法思路：首先判断顶点V1和V2是否是图的顶点，V1和V2是否存在边。如果V1和V2不是图的顶点，V1和V2存在边，不作处理。然后，判断V的值是否为1，为1不作处理。否则，先分配一个邻接表结点，其adjvex域是V2在adjList数组中的索引号，然后把该结点插入到顶点V1的邻接表的表头；然后再分配一个邻接表结点，其adjvex域是V1在adjList数组中的索引号，然后把该结点插入到顶点V2的邻接表的表头。4）DelEdge(Node<T>V1,Node<T>V2)方法

算法思路：首先判断顶点V1和V2是否是图的顶点，V1和V2是否存在边。如果V1和V2不是图的顶点，或V1和V2不存在边，不作处理。否则，先在顶点V1的邻接表中删除adjVex的值等于顶点V2在adjList数组中的序号结点，然后删除顶点V2的邻接表中adjVex的值等于顶点V1在adjList数组中的序号结点。

5）IsEdge(Node<T>V1,Node<T>V2)方法

算法思路：首先判断顶点V1和V2是否是图的顶点。如果V1和V2不是图的顶点，不作处理。否则，在顶点V1（或V2）的邻接表中查找是否存在adjVex的值等于V2（或V1）在adjList中的序号的结点，如果存在，则返回true，否则返回false。7.3图的遍历在前面的章节中，我们已经讨论过树的遍历，图的遍历和树的遍历类似。我们从图中的某个顶点出发，访问其余所有顶点，并且使每个顶点仅被访问一次，这个过程我们就成为图的遍历。图的遍历相对树来说要复杂一些，图中任意一个顶点都有可能和其他的顶点相邻接。所以在访问过程中，可能沿着某个顶点访问，然后又回到某个顶点，这样就存在回路，我们要避免访问同一个顶点多次的情况。为了解决这个问题，我们给每个已访问过的顶点做个记录。因此，可以设计一个数组visited[n]，n为图中顶点的数量，数组的值为1，表示已访问过；如果数组的值为0，表示没访问过。图的遍历有两种方法，一种是深度优先搜索法，另外一种是广度优先搜索法。深度优先搜索法图的深度优先搜索法（Depth_FirstSearch）类似与树的先序遍历。优先搜索法的基本思想是：先访问制定的起始顶点Vi；然后在与Vi相邻的未访问过的顶点中选择一个Vj进行访问；在与Vj相邻的未访问过的顶点中选择一个访问；直到某个顶点不存在未被访问的邻接顶点为止，则退回到最近被访问的顶点；如果它还有未被访问的邻接顶点，则选择一个未被访问过的顶点继续访问；如此循环重复，直到全部顶点都被访问到了再结束。例：无向图G9和有向图G10，从顶点V1出发，用深度优先搜索法遍历。深度优先搜索算法下面以无向图的邻接表存储结构为例来实现图的深度优先搜索法。

我们需要在无向图邻接表类中设计一个数组visited[n]，n为图中顶点的数量，数组中的初始值都设置为0，表示已未被访问过；如果数组中的值变为1，则表示已访问过。如果顶点Vi被访问，那么visited[i-1]的值为1。把该数组成员加到无向图的邻接表GraphAdjList<T>类中，增设visited成员字段，需要修改构造函数中的代码见教材。广度优先搜索法图的广度优先搜索法（BreadthFirstSearch）类似于树的层次遍历。图的广度优先搜索法的基本思想是：首先访问指定的某个起始顶点Vi；然后依次访问Vi的所有未被访问过的邻接顶点；在依次访问与Vi逐个邻接顶点的所有未被访问过的顶点。重复这个过程，直到所有的顶点都被访问完了再结束。例:无向图G9和有向图G10，从顶点V1出发，用广度优先搜索法遍历。广度优先搜索算法广度优先搜索法跟深度优先搜索法类似，我们需要在无向图邻接表类中设计一个数组visited[n]，n为图中顶点的数量。因为广度优先搜索法是分层访问，为了顺序访问各层，把访问路径长度为1，2，…，i的顶点放在一个队列cq中，队列是循环队列，队列中专门用来存放已经访问过的路径长度为1，2，…，i的顶点。循环队列类的定义见教材。以无向图的邻接表存储结构为例来实现图的广度优先搜索法，算法见教材。7.4最小生成树

最小生成树的应用很广泛，例如设计总长度最小的地铁线路，把若干商圈、写字楼和居民集中区连接起来；铺设地下供水供电供气的地下管道，如何使得造价最省；建立城市间通信网络，节省经费设备开销等。这些问题都涉及到最小生成树，为了解决这些问题，我们需要了解连通图、非连通图、最小生成树的概念和最小生成树算法。1、连通图、非连通图、最小生成树的概念例：通过深度和广度优先搜索法生成树。7.4最小生成树

2、最小生成树算法

构造有n个顶点的图的最小生成树必须必须满足以下几个条件：必须包括n个顶点，最小生成树中有且仅有n-1条边，最小生成树中不存在回路。生成最小生成树的方法有很多，典型的方法是普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。7.4最小生成树

1）普里姆(Prim)算法

假设有一个无向图G=(V，E)，其中V为图中顶点的集合，E为图中边的集合。最后得到的最小生成树，用U表示图G中最小生成树的顶点的集合，T为图G中最小生成树的边的集合。普里姆算法的设计思路是，先初始化顶点集U为V1，边集T的初始值为空；再从所有顶点集V中找出顶点Vi和Vj，并且在边集E中选出具有最小权值的边(Vi，Vj)，将顶点Vj加入到顶点集U中，将边(Vi，Vj)加入到边集T中。重复到U=V时，最小生成树构成。此时顶点集中存放在最小生成树的所有顶点，边集T中存放着最小生成树的所有边。7.4最小生成树

例:有向图G11为例，描述普里姆算法如何构成最小生成树。7.4最小生成树

2）克鲁斯卡尔(Kruskal)算法

克鲁斯卡尔算法的设计思路是，先假设有n个顶点，e条边的图G，分两种情况处理。第一种情况，如果图中的边数e=n-1，则G为最小生成树；否则一定有e>n-1。将图G中的边按照权值升序排列。第二种情况，将图G中的边都去掉，只留下n个顶点作为初始树，再按照边的排放顺序逐个查看，如果当前树中边的集合E(T)中的边不构成圈，则将它加入E(T)中，回到E(T)中满足n-1条边为止。7.5最短路径

图和网络这种数据结构，除了生成最小生成树的应用外，还有一个非常典型的应用就是最短路径问题。解决最短路径问题中典型的案例就是交通出行问题。十年来，我国的公路通车里程已经超过了410万公里，足够绕地球100圈；我国铁路的运营总里程已经超过了10万公里，每天都在以超过6公里的速度延伸，而其中的高铁运营里程已经突破1万公里，位居世界第我国各大小城市已互通国内航空航班，很多大城市与国外已互通国际航班；还有水上交通工具等。有如此多的选择，我们在出行旅游时，经常会考虑路费开销，从哪条线路，采用什么交通工具，花最少的钱最少的时间达到目的地？单源点最短路径

最短路径是求某个源点到其他顶点的最短路径，也可以是图中任意两个顶点之间的最短路径。单源点最短路径(MonophyleticPointShortestPath)是，在给定的一个单源点和一个有向图中，求出该源点到其他各个顶点之间的最短路径。例:有向图G12，设顶点V1为源点，求单源点的最短路径。

狄克斯特拉算法

求单源点的最短路径问题，一般是在带权的有向图中处理这种问题。迪克斯特拉算法的设计思路是，对于一个带权的有向图G，先设置一个源点Vi，再设置两个顶点集合S和T，顶点集S中存放已找到最短路径的顶点，顶点集T中存放还没找到最短路径的顶点。在初始状态时，顶点集S中只包含Vi，顶点集T中包括其余所有顶点，Vi对应的权值为0；然后再从顶点集T中选择到源点Vi路径最短的顶点u，把u加入到顶点集S中，要对顶点集T中的各个顶点的权值进行一次修改；若加进来的顶点u是中间顶点，使<Vi,u>+<u,Vj>的权值小余<Vi,Vj>的权值，则用<Vi,u>+<u,Vj>代替原来Vi的权值，修改后再在顶点集T中选取权值最小的顶点加入到顶点集S中；重复此过程，直到顶点集T中的顶点都加到顶点集S中为止。例:用狄克斯特拉算法求带权有向图从某个源点到其余顶点最短路径的过程。狄克斯特拉算法实现

要实现狄克斯特拉算法，首先要实现有向图邻接矩阵类，用来存放图的顶点和权值。再用狄克斯特拉算法实现单源点最短路径问题的解决方案。有向图邻接矩阵类DirNetMatrix<T>中必须包括三个成员字段，第一个是用来存放有向图中顶点信息的一维数组nodes，第二是表示有向图的邻接矩阵的二维数组mat，用来存放弧的信息的信息，第三个是num，表示有向图中弧的数量。有向图邻接矩阵类DirNetMatrix<T>实现见教材。所有顶点对之间的最短路径

顶点对之间的最短距离是指给定有向图中任意两个有序顶点的相互之间的最短距离。如有向图G=(V,W)，G中任意一对顶点Vi,Vj之间互相连接，找出Vi到Vj和Vj到Vi的最短距离。单源点的最短路径是指定一个源点，求源点与其他各个顶点之间的最短距离，采用的是狄克斯特拉算法。顶点对之间的最短路径问题，需要在狄克斯特拉算法的基础上改进，轮流以每个顶点为源点，重复执行狄克斯特拉算法n次。还有一个解决方案就是佛洛伊德(Floyed)算法。弗洛伊德算法

弗洛伊德算法的设计思路:

初始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，用max表示，当k=0时，mat[i,j]=path[i,j];然后逐步在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度短，则用新路径代替原路径，修改矩阵元素。比如，先让所有边加上中间顶点V1，取mat[i,j]与mat[i,1]+mat[1,j]中较小的值作mat[i,j]中的值，完成后得到第一次结果mat[n,n]矩阵；如此循环k次，得到最后的结果就是顶点Vi到顶点Vj的最短距离。

在用弗洛伊德算法求最短路径时，为方便求出中间经过的路径，设置二维数组path[n,n]，其中path[i,j]是相应路径上顶点j的前一顶点的顶点号。例:有向带权图G13，用佛洛伊德算法求顶点对的最短路径。

7.6拓扑排序拓扑排序(TopologicalSort)，是图的一个重要的应用，在实际工程或任务进行时应用非常广泛。比如大型工程的施工或生产作业流程，常常需要划分成若干个工作任务和工作流程，有的任务要先后作业，有的任务要并行作业，这些任务之间的先后顺序可以借助有向图来表示：顶点表示任务，有向边表示任务之间的先后顺序，我们把这种图叫做活动的图(ActiveOnVertexNetwork)，简称AOV网。在AOV网中，若从顶点Vi到顶点Vj之间存在有向边，则称Vi是Vj的前驱，Vj是Vi的后继。若<Vi,Vj>是AOV网中的弧，则称Vi是Vj的直接前驱，Vj是Vi的直接后继。

7.6拓扑排序例:如下表购物网站操作流程的先后顺序，有的操作可以先进行，有的操作要后进行，如何用AOV网表示这些操作之间的关系。购物网站操作流程

实训项目【实训】图的遍历1.实训说明涉及图的操作的