《图论》

 
 

一、关于图

1.图是什么

图是四类基本逻辑结构集合、线性结构、树形结构和图结构里面的其中一种，即图结构，图结构也是其中最为复杂的结构。在图的结构中，任意两个结点之间都可能相关，即结点之间的邻接关系是任意的。而在树形结构中，结点之间具有层次关系，每一层结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。图的结构可以描述多种复杂的数据对象，应用较为广泛。

2.图用来干什么

在现实生活中有很多实际问题可以用图的结构表示，进而可用计算机加以处理。如下是现实生活中几个常见的需求：

问题1 在N个城市间建立通信网络，使得其中的任意两个城市之间有直接或间接的通信线路，假设已知每两个城市之间通信线路的造价，如何设计出一个总造价最低的通讯网络？

 

问题2  在旅游的时候，从某地出发，要到某个目的地，如何选择路径，才能使得路程最短？如下图1-1所示，假如要从A点到G点，要怎么走才能使路径最短？

问题3  大学课程里，有些课程是基础课，它们可以独立于其他课程，即无前导课程，无先后关系；而有些课程必须在某些基础课程学完后才能开始学习，有先后关系。如何找出课程的学习流程图，以便科学合理的安排学习计划？

关于这些问题，可以用图论的方法来解决。解决这些问题首先需要弄清几个问题：

  如何描述这些问题的数据？

  如何在计算机中存储这些数据？

  解决问题的算法是什么？

例如，问题1可以用图结构来描述通信网络，用一个小圆圈代表一个城市，用小圆圈之间的连线代表对应两个城市之间的通信线路，在连线旁边附加一个数值表示该通信线路的造价。图1-2a是一种可能的通信网络建造初步方案，优化后的方案是图1-2b。

 

 

3.图的定义和术语

  有向图、无向图：图G由两个集合V和E组成，记为G=(V,E)，其中，v是顶点的有穷非空集合；E是边的集合，边是v中顶点的偶对。若顶点的偶对是有序的则称此图为有向图，有序偶对用尖括号<>括起来；反之，若顶点偶对是无序的，则称此图为无向图，无序偶对用圆括号（）括起来。

  弧、弧头、弧尾：有向图的边称为弧。如下图1-3a、b所示。

 

 

 

  权、带权图：图的边附带数值，这个数值叫权。每条边都带权的图称为带权图。

  顶点的度、入度、出度：无向图中顶点v的度是与该顶点相关的边的数目。如果图是一个有向图，则把以顶点v为终点的弧的数目称为v的入度，把以顶点v为始点的弧的数目称为v的出度，入度+出度=有向图的度。

  子图：设G=(V,E)是一个图，若E’是E的子集，V’是V的子集，并且E’中的边仅与V’中的顶点相关联，则图G’=(V’,E’)称为图G的子图。

  路径、路径长途：无向图的路径是一个顶点到另一个顶点所经过的边，所经过的边的数目称为路径长度；有向图的路径是一个顶点到另一个顶点的弧，路径长度是路径上面弧的数目。

  连同、连通图、连通分量：在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果图中的任意两个顶点vi和vj都是连通的，则称此图为连通图，如图1-4a。连通分量是无向图中的极大连通子图，如图1-4b是一个非连通图的两个连通分量。

 

 

  强连通、强连通图、强连通分量：对于无向图，如果图中任意一对顶点vi和vj(i!=j)都有顶点vi到vj的路径也有vj到v¬的路径，即两个顶点双向连通，那么称该有向图为强连通图。有向图的极大强连通子图称为强连通分量，如图1-5所示。

 

  生成树、生成森林：一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图。若连通图G的顶点个数为n，则G的生成树的边数为n-1。如果G的一个子图G’的边数大于n-1，则G’中一定有环。相反，如果G’的边数小于n-1，则G’一定不连通。在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树，这些连通分量的生成树组成了一个非连通图的生成森林。

 

二、图的存储结构

图有多种存储结构。例如，邻接矩阵、邻接表、十字链表和邻接多重表等，本文章以邻接矩阵为基础解决图的一些应用问题。

1.邻接矩阵

邻接矩阵就是用矩阵来描述图中顶点之间的关联关系，在程序设计语言中我们用二维数组来实现矩阵。设G=(V,E)是一个图，其中V={v0, v1,…, vn-1}，那么G的邻接矩阵A可定义成如下的n阶方阵：

 

如下图2-1a的M1和2-1b的M2分别是无向图的矩阵和有向图的矩阵。

 

值得注意的是无向图的邻接矩阵是一个对称矩阵，如图M1是以红色箭头为界限的对称结构。

 

利用邻接矩阵可以判定任意两个顶点之间是否有边，并容易求得各个顶点的度。对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的边数和。对于有向图，顶点vi的入度是邻接矩阵中第i列的边数和，出度是顶点vi所对应的行的边数和。利用这些已知条件，可以判定某个顶点是否有邻接结点。

三、图的遍历方法

图的遍历是指从图的某个顶点出发，系统地访问图的每个顶点，并且每个顶点只被访问一次。遍历图的基本方法有两种：深度优先搜索和广度优先搜索。此两种方法都适用于有向图和无向图。图的遍历操作类似于树的遍历操作。需要特别说明的是，遍历和搜索是两个不同的概念，图的遍历是访问图的每个顶点一次且仅一次，而搜索是从一个顶点出发访问到所有能访问的顶点一次且仅一次。

1.深度优先搜索

(1)基本思想

假定以图中某个顶点vi为出发点，首先访问出发点vi，然后任选一个vi的未访问过的邻接点vj，以vj为新的出发点继续进行深度优先搜索，依次类推，直至图中所有顶点都被访问过。深度优先搜索类似于树的先序遍历，如下图所示。

 

 

注意：

  搜索到达某个顶点时（图中仍有顶点未被访问），如果这个顶点的所有邻接点都被访问过，那么搜索就要回到前一个被访问过的顶点，再从该顶点的下一个未被访问过的邻接点开始深度优先搜索。图的深度优先搜索访问具有后进先出的特征，因此在使用java语言实现的时候可以采用栈来实现。

  深度优先搜索的顶点的访问序列不是唯一的。如图3-2的访问序列还可以是：广州->深圳->东莞->佛山->珠海等。

 

 

2.广度优先搜索

(1)基本思想

从图中某个顶点vi出发，在访问了vi之后依次访问vi的所有邻接点，然后依次从这些邻接点出发按广度优先搜索方法遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。广度优先搜索类似树的按层次遍历过程。如下图所示。

 

注意：

  若对x的访问先于y，则对x的邻接结点的访问也先于对y的邻接点的访问，也即广度优先搜索邻接点的寻找具有先进先出的特征，使用java语言实现的时候可以使用队列来实现。

  和深度优先搜索一样，图的顶点访问序列不是唯一的，如图3-4的广度优先搜索的访问序列还可以是：广州->佛山->深圳->东莞->珠海等。

四、图的应用

1.最小生成树

连通图的一次遍历所经历边的集合及图中所有顶点的集合就构成该图的一棵生成树。而连通图的遍历序列并不是唯一的，所以能得到不同的生成树，这些生成树就构成了图的生成森林。图的最小生成树就是从生成森林中找出权总和最小的生成树。

注意：对于有n个顶点的无向图，所有生成树中都有且仅有n-1条边。

构造最小生成树的两种基本方法是：Prim（普里姆）算法和Kruskal（克鲁斯卡尔）。

 

使用图的最小生成树可以解决文章开头的在城市之间建立通讯网络问题。

(1)Prim算法

1)基本思想

假设G=(V,E)是一个带权图，生成的最小生成树为MinT=(V,T)，其中V为顶点集合，T为边的集合。求边的集合T的步骤如下：

初始化：U={u0}，T={}。其中U为一个新设置的顶点集合，初始U中只含有顶点u0，即在构造最小生成树时从顶点u0出发；

对所有u∈U，v∈V-U（其中u,v表示顶点）的边(u,v)中，找一条权值最小的边(u’,v’)，将这条变加入到集合T中，将顶点v’加入集合U中。在使用Java语言实现时，本文采用Map键值对存储空边和边的终点所对应的顶点。

 

如果U=V，则算法结束；否则重复以上两个步骤。

2)算法执行示例图

初始状态：U={A}V={B,C,D,E,F,G}E={}

集合U和集合V相关联的顶点中权值最小的是AD，将D加入U。U={A,D} ，V={B,C,E,F,G}，E={AD}

集合U和集合V相关联的顶点中权值最小的是DF，将F加入U。{A,D,F}，V={B,C,E,G}，E={AD,DF}

 

 

集合U和集合V相关联的顶点中权值最小的是AB，将B加入U。U={A,D,F,B}，V={C,E,G}，E={AD,DF,AB}

 

集合U和集合V相关联的顶点中权值最小的是BE，将E加入U。U={A,D,F,B,E}，V={C,G} ，E={AD,DF,AB,BE}

集合U和集合V相关联的顶点中权值最小的是EC，将C加入U。U={A,D,F,B,E,C}，V={G} ，E={AD,DF,AB,BE,EC}

集合U和集合V相关联的顶点中权值最小的是EG，将G加入U。U={A,D,F,B,E,C.G}，V={} ，E={AD,DF,AB,BE,EC,EG} 所有顶点访问完毕。
 
上图是以A为出发点，访问每一个顶点，且代价最小的寻找过程。现在可以回答问题1里面的问题，在城市A到城市G之间建造通讯网络，代价最小的方案为：

A-->D=5

D-->F=6

A-->B=7

B-->E=7

E-->C=5

E-->G=9

总代价是39

(2)Kruskal算法

1)基本思想

 设G=(V,E)，令最小生成树初始状态只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量；

在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则，舍去此边，选区下一条代价最小的边；

依次类推，重复第二步，直至T中所有顶点都在同一连通分量上位置。

算法执行过程如图4-2所示。

2)算法执行示例图

  

2.单源最短路径

单源最短路径是计算有向图带权图的某一源点到其他各顶点的最短路径长度。单源最短路径和构造最小生成树类似。单源最短路径方法可解决文章开头处的旅游路线问题2。

(1)Dijkstra算法

 

1)背景

Dijkstra 即 艾兹格•迪科斯彻。艾兹格•W•迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日）荷兰人。 计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。

 

2)基本思想

设置顶点集合S，开始时S中只含有源点v。设u是G的某一个顶点，把从源点v 到u且中间只经过S中顶点的路径称为从源点到u的特殊路径，并用集合记录当前从源点v到其他每个顶点所对应的最短特殊路径长度以及路径经过的顶点。

 

3)算法执行示例图

以文章开头处的问题2为例，求从A点到G点的最短特殊路径，在这里将求出A点到其他任意一个顶点的最短特殊路径，如果需要指定目的地，可对程序做一些小处理就可以达到目的。

表4-1 Dijkstra算法的迭代过程状态变化

 
从表中可以看出从A点到其他每个顶点的特殊路径的变化状态。整个过程共有7步：

第1步，初始化（A,B），（A,C），（A,D），（A,E），（A,F），（A,G）三条变（或有向图的弧）的距离值，分别为dist[B]、dist[C]、dist[D]、dist[E]、dist[F]、dist[G]，分别是顶点A到其他每个顶点初始状态的最短距离。可以看出，A到D的距离最短，长度为5；

第2步，从V集合里取出顶点D加入到集合S中，由于顶点D加入了S，从A经过D到B的距离比A直接到D的距离小，不需要调整dist[B]，从A经过D到C与A直接到C都不可达，无需调整，从A经过D到E比从A直接到E小（AE=MAX），因此需要调整E的值为dist[E]=20，A经过D到F比A直接到F的值要小（A->F=MAX），因此调整dist[F]=11，A经过D到G与A直接到G都不可达，不调整；

第3步，在剩余的顶点集合V里面得出与A最小距离的顶点是B，因此将顶点B从V集合中取出加入S集合，接着重复第2步，直到所有顶点都加入集合S，此时求单源最短路径结束，第7步则是顶点A到其他每个顶点的最短路径，最后结果如下：

A-->D  权值=5

A-->B  权值=7

A-->F  权值=11

A-->E  权值=14

A-->C  权值=15

A-->G  权值=22

顶点访问序列：{A,D,B,F,E,C,G}

现在可以回答文章开头处的问题2，从A到G的最短路径是22。

3.拓扑排序

若在有向图G中，从顶点vi到vj有一条路径，则在拓扑序列中顶点vi必须排在顶点vj之前。找一个有向图的一个拓扑序列的过程称为拓扑排序，而完成拓扑排序的前提条件是AOV网中不允许出现回路。AOV网络：工程或者某种流程可以分为若干个小的工程或结点，这些小的工程或阶段就称为活动。如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶点表示活动的有向图称为AOV网。如图4-1就是课程之间先后关系的AOV网。拓扑排序可以解决文档开头的问题3。

表4-2课程之间的先后关系

 

 课程之间的先后关系用有向图表示如图4-3所示。

 

1)基本思想

  在图中选择一个入度为0的顶点，输出该顶点；

  从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度减1）；

 

  重复执行上述两步，直到所有入度为0的顶点均被输出，拓扑排序完成，或者图中再也没有入度为0的顶点。

2)算法执行流程图

从图可以看出，由于在排序过程中顶点的入度是随时调整的，因此拓扑排序输出序列并不是唯一的，所以答案也不是唯一的。按照上图的步骤得到的答案是：

C1->C7->C6->C2->C3->C4->C5

五、心得与体会

本文章解释了图是什么、图的邻接矩阵存储结构、图的深度优先搜索与广度优先搜索的

遍历方法以及图在生活中的一些实际应用。

 

图论能够解决生活中许多实际问题。通过学习图的一些术语、存储结构、遍历方法以及实际应用过程中的经典算法，深刻体会到图作为几种基本的逻辑结构中最为复杂的一种结构。然而图结构虽然复杂，但只要根据科学的理论依据以及利用正确的方法将复杂的问题逐步分解，各个击破，再复杂的问题都能迎刃而解。

 

要理解别人的算法理论依据，还要将算法转化为计算机程序，这些过程可能会遇到各种困难。就好比软件开发中的两个转换困难：用户的理解到程序员的理解之间的困难；程序员的理解到计算机程序的实现之间的困难。在实现程序的过程中首先要理解算法的理论依据，然后观察算法执行过程中的状态变化，最好是画出每一步的执行步骤，数据之间在什么时候转化，转化的条件是什么，把这些问题一一弄清楚之后，再来写程序就会得心应手。

 

六、Java版实现代码

本文档所述的算法：广度优先搜索、深度优先搜索、Prim算法、Kruskal算法、Dijkstra算法、拓扑排序都已经使用Java语言通过邻接矩阵实现，且经过调试成功。

 

邮箱:[e-mail]

 

附录A  参考文献

 

[1]郑诚.数据结构导论[M].外语教学与研究出版社，2012