扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
【离散数学】 下面四组数能构成无向简单图的度数序列有（）A、（2,2,2,2,2 ） B、（1,1,2,2,3） C、（1,1,2,2,2） D、（0,1,3,3,3）
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
C,首先度数总和应为偶数,所以B不对,然后是D不能构成图,也不能选,A构成的图是一个环,不是简单图,所以选C.
为您推荐：
其他类似问题
扫描下载二维码图结构 - 简书
一、关于图
1.图是什么
图是四类基本逻辑结构集合、线性结构、树形结构和图结构里面的其中一种，即图结构，图结构也是其中最为复杂的结构。在图的结构中，任意两个结点之间都可能相关，即结点之间的邻接关系是任意的。而在树形结构中，结点之间具有层次关系，每一层结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。图的结构可以描述多种复杂的数据对象，应用较为广泛。
2.图用来干什么
在现实生活中有很多实际问题可以用图的结构表示，进而可用计算机加以处理。如下是现实生活中几个常见的需求：
在N个城市间建立通信网络，使得其中的任意两个城市之间有直接或间接的通信线路，假设已知每两个城市之间通信线路的造价，如何设计出一个总造价最低的通讯网络？
在旅游的时候，从某地出发，要到某个目的地，如何选择路径，才能使得路程最短？如下图1-1所示，假如要从A点到G点，要怎么走才能使路径最短？
大学课程里，有些课程是基础课，它们可以独立于其他课程，即无前导课程，无先后关系；而有些课程必须在某些基础课程学完后才能开始学习，有先后关系。如何找出课程的学习流程图，以便科学合理的安排学习计划？
关于这些问题，可以用图论的方法来解决。解决这些问题首先需要弄清几个问题：
如何描述这些问题的数据？
如何在计算机中存储这些数据？
解决问题的算法是什么？
例如，问题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之间建造通讯网络，代价最小的方案为：
总代价是39
(2)Kruskal算法
1)基本思想
?设G=(V,E)，令最小生成树初始状态只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量；
?在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则，舍去此边，选区下一条代价最小的边；
?依次类推，重复第二步，直至T中所有顶点都在同一连通分量上位置。
算法执行过程如图4-2所示。
2)算法执行示例图
2.单源最短路径
单源最短路径是计算有向图带权图的某一源点到其他各顶点的最短路径长度。单源最短路径和构造最小生成树类似。单源最短路径方法可解决文章开头处的旅游路线问题2。
(1)Dijkstra算法
Dijkstra 即 艾兹格o迪科斯彻。艾兹格oWo迪科斯彻 （Edsger Wybe Dijkstra，日~日）荷兰人。 计算机科学家，毕业就职于荷兰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,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实现代码，如有需要可交流联系！
图是数据结构里面的重要一章。通过图，我们可以判断两个点之间是不是具有连通性；通过图，我们还可以计算两个点之间的最小距离是多少；通过图，我们还可以根据不同的要求，寻找不同的合适路径。当然，有的时候为了计算的需要，我们还需要从图中抽象出最小生成树，这样在遍历计算的时候就不需要持续判断是不是遇到了循环节点。当然，这所有的一切都是从图的表示开始的。
1）矩阵表示
矩阵表示可以说是最简单的表示方法，如果说一个图中有5个点，那么我们就可以构建一个55的矩阵。如果点和点之间存在连接，那么填上1；反之如果不存在连接，那么可以用0表示，当然对角线上面的点是没有意义的。如下图所示：
[cpp] view plain copy
static int graph[5][5] =
{0, 1, 0, 1, 1},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{1, 1, 0, 1, 0}
如果点和点之间还是存在方向的，那么它们关于(x，x)对称轴就是不对称的，所以结果也可能是这样的：
[cpp] view plain copy
static int graph[5][5] =
{0, 0, 0, 0, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 1, 0}
当然，如果点和点之间的关系存在某种权重，比如说距离，那我们可以用它来代替原来的数据1：
[cpp] view plain copy
static int graph[5][5] =
{0, 0, 0, 0, 0},
{3, 0, 0, 0, 0},
{0, 6, 0, 0, 0},
{8, 0, 4, 0, 0},
{9, 2, 0, 7, 0}
矩阵表示下的图结构非常直观。但是，矩阵有一个特点，就是比较浪费空间。因为我们这里举例的顶点比较少，只有5个，但是请大家试想一下，如果一张图上有10000个节点，那么1000010000该是多大的一个空间啊。重要的是，这上面大多数点都是0，所以浪费的空间是相当可观的。
2）数组结构
为了改变矩阵浪费空间的特点，我们可以建立一个只有顶点和边组成的数据空间。比如说，我们定义一个这样的结构：
[cpp] view plain copy
typedef struct _LINE
上面定义的数据结构非常简洁。第1个为起始顶点，第2个为终点，第3个为权重，第4个判断当前边是否有向。图中要是有多少边，我们就要定义多少个这样的数据。如果把这些边的数据都放在一起构成一个数组，那么我们就可以用这个数组来表示图的全部信息了。
但是，我们还是觉得有遗憾的地方。这个数据结构过分强调了边的意义和重要性，忽略了顶点本身的含义。因为，我们在强调边的时候，应该添加进顶点的相关特性。离开顶点的支持，单纯的边信息是没有什么含义的。
3）基于顶点链表的图表示
首先，我们定义顶点的基本结构：
[cpp] view plain copy
typedef struct _LINE
struct _LINE*
typedef struct _VECTEX
我们用VECTEX记录顶点的相关信息，LINE表示节点的相关信息。如果LINE是在VECTEX中的变量，那么neighbor表示当前所有节点的起始点都是start点。如果它是PATH中的变量呢，那么next的起始点就是LINE链接的前面一个点，不知道我讲清楚了没有？下面就是点与点之间PATH的定义。
[cpp] view plain copy
typedef struct _PATH
其中start为起始点，end为终结点，next为start链接的下一个点，lenth为路径的总长度，当然也可以修改成其他的权重形式。
注意事项：
1）数组和链表是图结构的基础，朋友们应该好好掌握
2）每一种数据结构都有自己的应用场合，关键是理解其中的思想和方法
3）图的表示是图运算的基础，掌握它们是我们进一步学习的基本条件
[TOC] Class I. Words Expressing Abstract Relations Section I. Existence 1. Being, in The Abstract existence 1 absolute
a.绝对的，完全的; 无(条件...
第一章 绪论 什么是数据结构？ 数据结构的定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章 算法 算法的特性：有穷性、确定性、可行性、输入、输出。 什么是好的算法？ ----正确性、可读性、健壮性、时间效率高、存储量低 函数的渐近增长：给定两个函数f...
图的抽象数据结构 图：表示多对多的关系，包含一组顶点，采用V表示顶点集合，以及一组边，采用E表示边集合，边为顶点对；无向图：所以边均为无向有向图：存在边为有向抽象数据类型: 图的表示形式：邻接矩阵 ：G[i][j]=1 (i,j存在一条边，其余为0)，直观、容易理解，亦寻找...
图的概念 图是一种非线性的数据结构,一个图中有两类东西，一种是结点，一种是边.我们用V这个集合来表示节点（vertex），还需要另一个集合来存储所有的边，我们用E来表示(Edge)，那么一个图就可以表示为：G=(V,E);带箭头的称为有向图,否则称为无向图.如果一个图的任意...
图是一种比线性表和树更复杂的数据结构，在图中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。图是一种多对多的数据结构。 1、基本概念 2、图的存储结构 2.1、邻接矩阵 2.2、邻接表 2.3、十字链表 3、图的遍历 3.1、深度优先遍历 3.2、广度优先遍历 4...
这家店 因为吃了好多次， 每次觉得真的猴猴吃， 每次吃的东西还都不一样， 所以记录下来和大家分享！ 但是我去吃的时候并没有想要写文章啊！ 只是想秀图片啊！ 所以好多必备场景图比如环境呀，菜品介绍呀，动手制作的过程图啦都没有拍， So请理解我当初只想做个逛吃逛吃拍照拍照的初级...
心眼这个东西很难懂啊！ 想多了吧，小心眼， 想少了吧，没心眼， 不想了吧，缺心眼。 现在的社会，现在的人， 都是喜欢虚假的。 会做的不如会说的， 会说的不如会混的。 真情可贵，用心赔罪， 虚伪面对，从容领会， 我是永远都学不会 谁的评价都无所谓， 活着只求问心无愧！ 对的起...
武陵山区秋至冬，伐薪烧炭乐其中，火子闭炭打脱火，柔弱书生是英雄。在湘西山区的乡村里，冬季取暖是在厨房旁大大的火坑里烧柴蔸蔸，在客厅的小火坑里就烧刨火炭，少数家庭条件好的就烧蔸蔸炭或硬炭。小孩上学提烘笼也是烧的木炭。因此家家户户都有闭炭，烧炭的习惯。 一、火子闭炭 我们在家煮...
河狸家起步于上门美甲，随后陆续开通了美睫、手足护理、化妆、美容等业务，未来还会把业务延伸至美发、写真摄影等更多让生活“美起来”的服务。 河狸家APP，使命是“解放天下手艺人”，为无数家庭带来便捷服务、御宅生活。 体验环境 产品版本：v2.0.7APP 设备型号：androi...
反思最近的学习情况，存在的最大问题就是学习不够系统，输入太多，但是输出太少，对所学的知识没有很好的消化吸收。学以致用这个道理大家都懂，但是做到的人还是太少，为了改善这个情况，我下一步学习重点应该是如何提高学习效率、进行知识管理、建立知识体系等等。为此，本着提高学习力的目的，...当前位置： >>
图结构》习题解答
第 7 章 图结构第7章本章学习要点图 结 构◆熟悉图的定义、相关术语以及基本概念 ◆熟练掌握图的 4 种存储结构，能根据实际问题选择合适的存储结构 ◆熟练掌握图的两种遍历方法 ◆理解并掌握最小生成树意义和两种算法 ◆理解并掌握查找最短路径的有关算法 ◆理解并掌握拓扑排序的有关算法 ◆理解并掌握查找关键路径的有关算法 在计算机科学、工程以及其它许多学科中，常常需要研究数据对象之间的各种关系。比 如，可以用线性表来表示数据对象之间的线性关系，用树结构来表示数据对象之间的某种层 次关系。但是，还有许多问题（比如信息通信网络）中的数据对象是不能用以上两种关系来 明确表示的，这就需要一种更为复杂的数据结构 ―图结构。图结构可以用来表示数据对象之 间的任意关系，图中的每个结点都可以和其它任一结点相连接，即图中数据对象之间的对应 关系是“多个对多个”的关系。 本章将详细介绍图的基本概念、各种存储结构、遍历方法，求图的连通分量、生成树、 最短路径，最后介绍一些有关图的应用问题。7.1 图的定义和基本术语7.1.1 图的定义图 G(graph) 是由两个集合 V 和 VR 组成，记为 G=(V,VR)。V 是顶点的有穷非空集合；VR 是定义在 V 上的所有关系（两个不同顶点之间的弧或边）的集合。VR 可以是空集合，当 VR 为空集时 G 表示集合类结构类型。如图 7.1(a)、(b)所示的是一个有向图和一个无向图。7.1.2 图结构的基本术语（1）顶点(Vertex) 图中的数据元素。比如，图 7.1 中的顶点有：v1,v2,v3,v4,v5,v6。 （2）弧(Arc) 设 VR 是图中所有顶点之间的关系集，若&v,w&∈VR，则&v,w&表示从顶点 v-.167.-第 7 章 图结构到顶点 w 的一条弧。 例如， 在图 7.1(a)所示的图 G 中的弧有： &v1,v2&,&v1,v4&,&v3,v1&,&v3,v6&,&v4,v3&,&v5,v4& 和&v6,v5&,&v6,v1&共 8 条弧。 （3）弧尾(Tail) 弧的起始点。 （4）弧头(Head) 弧的终端点。一条弧用有序对符号“&弧尾，弧头&”来表示。 （5）有向图(Digraph) 由顶点和弧组成的图称为有向图。比如，图 7.1(a)表示一个有向图。 （6）边(Edge) 设 VR 是图中所有顶点之间的关系集，若&v,w&∈VR 必有&w,v&∈VR，则以无 序对符号(v,w)或(w,v)来代替&v,w&和&w,v&，表示顶点 v 与顶点 w 之间的一条边。 例如，在图 7.1(b)所示的图 G 中的边有：(v1,v2),(v1,v4),(v2,v3),(v2,v6),(v3,v5),(v4,v5)和 (v5,v6)共 7 条边。 （7） 无向图(Undigraph) 由顶点和边组成的图称为无向图。 比如， 图 7.1(b)表示一个无向图。 （8）完全图(Completed graph) 用 n 表示图中的顶点数，则具有 n(n-1)/2 条边的无向图称为 无向完全图；具有 n(n-1)条弧的有向图称为有向完全图。当图 G 中边(或弧)的总数 e 满足：e ? n log n 时，称其为稀疏图(sparse graph)；当 e 满足： e ? n log n 时称其为稠密图 (densegraph)。显然，完全图是稠密图，反之不然。图 7.2(a)所示为由 4 个顶点组成的无向完全图， 而图 7.2(b)则是由 3 个顶点组成的有向完全图。（9）权(Weight) 与图的边或弧相关的数（比如长度）称为权。 （10）网(Network) 具有权值的图称为网，带权的有向图称为有向网，带权的无向图称为无 向网。比如，图 7.3(a)表示的是一个有向网，而图 7.3(b)表示的是一个无向网。（11）子图(Subgraph) 假设有两个图 G=(V,E)和 G’=(V’,E’)，若 V’ ? V 并且 E’ ? E，则称 G’ 是 G 的子图。 例如，图 7.4(a)为有向图及其部分子图，图 7.4(b)为无向图及其部分子图。-.168.-第 7 章 图结构（12）邻接点(Adjacent) 对于无向图 G=(V,VR)，若边(v,w)∈VR，则称 v 和 w 互为邻接点， 边(v,w)依附(Incident)于顶点 v 和 w， 或者说边(v,w)与顶点 v、 w 相关联。 对于有向图 G=(V,VR)， 若弧&v,w&∈VR，则称顶点 v 邻接到顶点 w，顶点 w 邻接自顶点 v。 （13）度(Degree) 在无向图中，顶点 v 的度是指和 v 相关联的边的数目，记为 TD(v)。 （14）出度(Out degree)和入度(In degree) 在有向图中，顶点 v 的出度是指以 v 为弧尾的弧 的数目，记为 OD(v)；顶点 v 的入度是指以 v 为弧头的弧的数目，记为 ID(v)；顶点 v 的度是 指 v 的出度、入度的和，记为 TD(v)。 一般地，如果顶点 vi 的度记为 TD(vi)，那么一个有 n 个顶点 e 条边（或弧）的图，必定满 足关系如下： 1 n e ? ? TD(vi ) 2 i ?1 （15）路径(Path) 在图中，从顶点 v 到顶点 w 的顶点序列称为路径。显然，有向图的路径 是有向的。路径长度是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为简单路 径。 （16）回路或环(Cycle) 在路径的顶点序列中，第一个顶点和最后一个顶点相同的路径称为 回路。除了第一个顶点和最后一个顶点外，其余顶点均不重复出现的回路称为 简单回路或简 单环。 例如，在图 7.4(a)所示的有向图中，顶点序列(v1,v3,v4,v1,v2)表示一条有向路径，由于其中 存在重复点 v1 所以不是简单路径，该路径的长度为 4；顶点序列(v1,v3,v4)表示一条有向路径， 并且是长度为 2 的简单路径； 顶点序列(v1,v3,v4,v1)表示一条有向路径并且是长度为 3 的简单回 路（或环） 。在图 7.4(b)所示的无向图中，顶点序列(v1,v3,v5,v4,v3,v5,v2)表示一条路径，由于其 中存在重复点 v3、v5 所以不是简单路径；顶点序列(v1,v3,v4,v5,v2,v1)是长度为 5 的简单回路。 （17）连通图(Connected graph) 在无向图 G=(V,VR)中，如果从顶点 v 到顶点 w 有路径，则 称 v 与 w 是连通的。如果对于任意两个顶点 v,w∈V 都是连通的则称 G 是连通图。 （18）连通分量(Connected component) 无向图 G 中的极大连通子图称为 G 的连通分量。图 7.5 给出一个无向图和它的 3 个连通分量的示例。（19） 强连通图 在有向图 G=(V,VR)中，如果对于任意两个顶点 v,w∈V，都存在一条 v 到 w-.169.-第 7 章 图结构的路径，则称 G 是强连通图；如果对于任意两个顶点 v,w ∈ V ，都存在一个顶点序列： v=v0,v1,v2,…,vk=w 满足&vi,vi+1&或&vi+1,vi&∈VR，则称 G 是弱连通图。 例如，图 7.1(a)为弱连通图，图 7.2(b)为强连通图。 （20）强连通分量 有向图 G 中的极大强连通子图称为 G 的强连通分量。图 7.6 给出一个有 向图和它的 2 个强连通分量的示例。说明： 在连通分量和强连通分量定义中的“极大”应理解为包含依附于该连通子图或强连通子图 中顶点的所有边或弧。 （21）生成树 一个无向连通图的生成树是一个极小连通子图，即它包含图中的所有（假设 n 个）顶点，但是只有足以构成一棵树的 n-1 条边。 说明： 1）一个无向连通图的生成树不是唯一的，所有生成树的顶点相同但是所包含的边可以不 同。 2）一棵有 n 个顶点的连通图的生成树有且仅有 n-1 条边。但是有 n 个顶点和 n-1 条边的 无向图不一定是生成树。 例如，图 7.7 给出一个连通图(图 7.7(a))和它的 3 棵生成树(图 7.7(b))的示例。（22）生成森林 如果一个有向图 G 恰有一个顶点的入度为 0，其余顶点的入度均为 1，则 G 是一棵有向树。一个有向图的生成森林由若干棵有向树组成，森林中含有图中全部顶点，但 是只有足以构成若干棵不相交的有向树的弧 。显然，一个有向图生成的有向树或生成森林都 不是唯一的。关于“顶点位置”的说明： 在图的基本操作定义中，其“顶点位置”和“邻接点位置”仅是一个相对的概念。从图的定义-.170.-第 7 章 图结构可以看出，图中所有顶点的位置都是平等的，可以将任意一个顶点看成是第一个或最后一个 顶点，也无法将其排列成一个线性序列或层次关系。在实际操作中，为了方便起见，需要将 所有顶点按照某个任意选定的顺序排列起来（排列与图中顶点之间的关系无关） 。所以，“顶点 在图中的位置”是指该顶点在这个人为的随意排列中的位置（或序号） 。同理，可以对某个顶点 的所有邻接点按照某个任意选定的顺序进行排列。7.1.3 图的基本操作对于图结构，常用的操作有以下几种： （1）创建 CreateGraph(&G,V,VR) 根据顶点集 V 和关系（边或弧）集 VR 构造图 G； （2）查找 LocateVex(G,u) 函数功能是，如果图 G 中存在信息等于 u 的顶点则返回该顶点在 G 中的位置，否则返回 0； （3）提取 GetVex(G,v) 函数功能是，返回图 G 中顶点 v 的信息； （4）修改 PutVex(&G,v,value) 函数功能是，修改图 G 中顶点 v 的信息为 value； （5）邻接点 FirstAdjVex(G,v) 函数功能是，返回图 G 中顶点 v 的第一个邻接点在 G 中的位 置，操作不成功时返回 0； （6） 下一个邻接点 NextAdjVex(G,v,w) 函数中 v,w 是图 G 的顶点， 且 w 是 v 的一个邻接点。 函数功能是，返回顶点 v 相对于 w 的下一个邻接点所在的位置，如果 w 是 v 的最后一个邻接 点则返回 0； （7）插入顶点 InsertVex(&G,v) 函数功能是，在图 G 中插入顶点 v； （8）删除顶点 DeleteVex(&G,v) 函数功能是，在图 G 中删除顶点 v 以及相关的边或弧； （9）插入弧 InsertArc(&G,v,w) 函数功能是，在图 G 中增加边(v,w)或弧&v,w&； （10）删除弧 DeleteArc(&G,v,w) 函数功能是，在图 G 中删除边(v,w)或弧&v,w&； （11）深度优先遍历 DSFTraverse(G,v,Visit()) 函数功能是，从顶点 v 开始按深度优先遍历图 G，其中 Visit()是关于顶点的操作函数； （12）广度优先遍历 BSFTraverse(G,v,Visit()) 函数功能是，从顶点 v 开始按广度优先遍历图 G，其中 Visit()是关于顶点的操作函数。7.2 图的存储表示与实现图是一种复杂结构其存储方法也比较多，在实际应用中，一般需要根据具体的图形和要 进行的操作来选取适当的存储结构。图的常用存储结构有：邻接矩阵表示法、邻接表表示法、 十字链表表示法和多重链接表表示法。7.2.1 邻接矩阵表示法邻接矩阵表示法是图的一种顺序存储表示法。用两个数组分别存储数据元素（顶点）的 信息和元素之间所存在的关系(边或弧)的信息。该表示法既可用于表示无向图也可用于表示有 向图。 1．邻接矩阵的定义-.171.-第 7 章 图结构设 G=(V,VR)是一个图，含有 n 个顶点，那么 G 的邻接矩阵是表示 G 中顶点之间相邻关系 的 n 阶方阵 An×n，下面分别根据有权图和无权图给出矩阵 A 的定义。 如果 G 是无权图，则 A 的定义为：?1 A[i ][ j ] ? ? ?0如果 G 是有权图，则 A 的定义为：(vi , v j ) ? VR 或 ? vi , v j ?? VR其它情况A[i ][ j ] ? ?? wij ?0(vi , v j ) ? VR 或 ? vi , v j ?? V（ 权值w ij ? 0） R其它情况(为操作统一此处用0而非? )【例 7.1】分别给出图 7.1、图 7.3 中各图的邻接矩阵。 在图 7.1(a)、图 7.1(b)中，图的顶点顺序按 v1 , v2 , v3 , v4 , v5 , v6 排列时的邻接矩阵分别如图 7.9(a)、图 7.9(b)所示；在图 7.3(a)、图 7.3(b)中，图的顶点顺序分别按 A, B , C , D 和 A, B, C , D, E 排列时的邻接矩阵分别如图 7.9(c)、图 7.9(d)所示。显然，图的邻接矩阵有以下特点： (1) 当图中顶点的排列顺序确定后，该图的邻接矩阵是唯一确定的； (2) 无向图的邻接矩阵是对称的，可以采用压缩存储的方法仅存入其下三角（或上三角）部 分的元素即可； (3) 在无向图中，顶点 vi 的度是其邻接矩阵 A 的第 i 行元素的和，即：TD(vi ) ? ? A[i ][ j ] ；j ?0 n ?1(4) 在有向图中，顶点 vi 的出度是其邻接矩阵 A 的第 i 行元素的和，而入度是 A 的第 i 列元 素的和，所以 vi 的度可以表示为： TD(vi ) ? ? A[i ][ j ] ? ? A[ j ][i] （n 为图中顶点的个数） 。j ?0 j ?0 n ?1 n ?12．邻接矩阵的存储表示与实现 (1)邻接矩阵的类型定义 typedef enum{DG,DN,UDG,UDN}GK//图的类型 GKind{有向图,有向网,无向图,无向网}-.172.-第 7 章 图结构typedef int VT struct VNode{VT}; struct MGraph{ VNode* VType* int vexnum, GK }; (2)查找图中顶点位置的操作 函数的功能是，返回顶点 u 在图 G 中的位置，查找失败返回 0 值。 int LocateVex_MG(MGraph G,VType u) { for(i=0;i&G.i++) if(G.vexs[i].vex==u) if(i&G.vexnum)return(i+1); else return(0); } (3)邻接矩阵的建立操作 函数的功能是，根据图 G 的种类标志 kind 建立图 G 的所有信息。 #include&iostream.h& void CreateGraph_MG(MGraph& G,GKind kind) { int i,j,k; VType u,v; cout&&&输入顶点数 vexnum 和弧数 arcnum:&; cin&&G.vexnum&&G. G.kind= G.vexs=new VNode[G.vexnum]; //为 G.vexs 分配存储空间 G.arcs=new VType[G.vexnum*G.vexnum]; //为 G.arcs 分配存储空间 cout&&&按某种顺序输入&&&G.vexnum&&&个顶点的值:\n&; for(i=0;i&G.i++) { G.vexs[i].flag=0; //flag=0 表示该顶点未被访问 cin&&G.vexs[i]. //输入所有顶点的信息到 G.vexs 中 } for(i=0;i&G.i++) //将图 G 的关系集 G.arcs 初始化为空集 for(j=0;j&G.j++) G.arcs[i*G.vexnum+j]=0; if(G.kind==DG||G.kind==UDG) cout&&&输入图中&&&G.arcnum&&&条边(弧)的信息 u v:\n&;//为便于操作，定义顶点类型 VType 为 int 型 //顶点与访问情况类型 VNode{访问次数,顶点信息} //定义图的邻接矩阵类型 MGraph //描述顶点的数组指针 vexs //邻接矩阵的数组指针 arcs //顶点数 vexnum 和边或弧数 arcnum //图的种类标志 kind-.173.-第 7 章 图结构else cout&&&输入图中&&&G.arcnum&&&条边(弧)和权的信息 u v w:\n&; for(k=0;k&G.k++) //输入图中所有边或弧的信息 { do{ cin&&u&&v; } //根据顶点信息找到所在位置 while(!((i=LocateVex_MG(G,u))&&(j=LocateVex_MG(G,v)))); i--,j--; //i,j 从位置值转换为下标值 G.arcs[i*G.vexnum+j]=1; if(G.kind==DN||G.kind==UDN) cin&&G.arcs[i*G.vexnum+j]; //输入相应边或弧的权重 w if(G.kind==UDG||G.kind==UDN) //无向图的邻接矩阵是对称的 G.arcs[j*G.vexnum+i]=G.arcs[i*G.vexnum+j]; } } (4)显示输出邻接矩阵的操作 函数功能是，显示输出图 G 的邻接矩阵 G.arcs。 void DisplyMG(MGraph G) { int i,j; for(i=0;i&G.i++) { for(j=0;j&G.j++) cout&&G.arcs[i*G.vexnum+j]&&' '; cout&& } } (5)演示程序主函数 程序中分别建立有向图 G1、无向图 G2、有向网 G3 和无向网 G4 的邻接矩阵，并显示输 出每个邻接矩阵的数据信息。 void main() { MGraph G1,G2,G3,G4; GKind gk1=DG,gk2=UDG,gk3=DN,gk4=UDN; cout&&&建立一个有向图的邻接矩阵 G1:\n&; CreateGraph_MG(G1,gk1); cout&&&建立一个无向图的邻接矩阵 G2:\n&; CreateGraph_MG(G2,gk2); cout&&&有向图 G1 的邻接矩阵为:\n&; DisplyMG(G1); cout&&&无向图 G2 的邻接矩阵为:\n&; DisplyMG(G2); cout&&&***************************************\n&; cout&&&建立一个有向网的邻接矩阵 G3:\n&;-.174.-第 7 章 图结构CreateGraph_MG(G3,gk3); cout&&&建立一个无向网的邻接矩阵 G4:\n&; CreateGraph_MG(G4,gk4); cout&&&有向网 G3 的邻接矩阵为:\n&; DisplyMG(G3); cout&&&无向网 G4 的邻接矩阵为:\n&; DisplyMG(G4); }程序运行演示结果为：建立一个有向图的邻接矩阵 G1: 输入顶点数 vexnum 和弧数 arcnum:6 8L 按某种顺序输入 6 个顶点的值: 1 2 3 4 5 6L 输入图中 8 条边(弧)的信息 u v: 1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5L 建立一个无向图的邻接矩阵 G2: 输入顶点数 vexnum 和弧数 arcnum:6 7L 按某种顺序输入 6 个顶点的值: 1 2 3 4 5 6L 输入图中 7 条边(弧)的信息 u v: 1 2 1 4 2 3 2 6 5 3 5 6 5 4L 有向图 G1 的邻接矩阵为: 000 000 010 无向图 G2 的邻接矩阵为: 001 010 010 *************************************** 建立一个有向网的邻接矩阵 G3: 输入顶点数 vexnum 和弧数 arcnum:4 4L 按某种顺序输入 4 个顶点的值: 1 2 3 4L 输入图中 4 条边(弧)和权的信息 u v w: 1 2 7 1 3 1 3 4 5 4 1 9L 建立一个无向网的邻接矩阵 G4: 输入顶点数 vexnum 和弧数 arcnum:5 5L 按某种顺序输入 5 个顶点的值: 1 2 3 4 5L 输入图中 5 条边(弧)和权的信息 u v w: 1 2 9 4 1 8 4 2 3 4 5 1 3 5 12 L 有向网 G3 的邻接矩阵为: 05 9000 无向网 G4 的邻接矩阵为: 0 9 0 8 0 9 0 0 3 0 0 0 0 0 12 8 3 0 0 1 0 0 12 1 0说明： （1）程序演示中建立的是图 7.1、图 7.3 中 4 个图的邻接矩阵：G1.arcs、G2.arcs、G3.arcs、 G4.arcs。从运行结果可以看出与图 7.9 的形式一致。 （2）在图的邻接矩阵存储结构上也容易实现其它基本操作，比如，对于无向图 G 中返回顶 点 v 的第一个邻接点位置的基本操作函数：int FirstAdjVex_MG(MGraph G,VType v)。 算法的实现过程是： 1) 根据顶点信息 v， 通过调用函数 int LocateVex_MG(MGraph G,VType v)找到 v 在 G 中的 位置 i； 2) 在 G 的邻接矩阵中寻找第 i 行中第一个非零元素所在的列号 j； 3) 如果 j 存在函数返回 j+1，否则返回 0 值。 类似地可以给出函数：int NextAdjVex_MG(MGraph G,VType v,VType w)的算法实现代码。 （3）用邻接矩阵表示有 n 个顶点的图 G 时，查找边（或弧）的时间复杂度为 O(n2)。由于 邻接矩阵的存储空间仅与顶点数 n 有关，而与边无关，因此，当图 G 的顶点较多而边数又很 少时，其边的查找效率会很低。为此，下面给出图的另一种存储结构，即图的邻接表表示法。-.175.-第 7 章 图结构7.2.2 邻接表表示法图的邻接表表示是把图的每个顶点的邻接顶点用一个链表来表示。一般地，用顺序存储 的方式来表示图中 n 个顶点的信息，另外，对图中每个顶点 v 建立一个单链表，用于表示与 v 相邻接的所有顶点的位置（下标） 。链表中每个结点有两个域值：一个是顶点位置（下标）域， 用于表示该邻接点的序号；另一个是指针域，用于指向下一个邻接点。 1．邻接表的定义 (1) 表结点 在邻接表中，对图中的每个顶点建立一个单链表，顶点 v 所对应的单链表中 的结点（表示依附于该顶点的边或以 v 为尾的弧）称为表结点。图的表结点中包含有顶点位 置域(adjvex)、指向下一条边（弧）的指针域（nextarc） ；而网的表结点中还要有表示相应权值 的域（weight） 。 (2) 头结点 在邻接表中每个单链表上附设一个结点，称为头结点。每个头结点由 3 个域 组成：结点信息域(data)、结点访问次数域(flag)和指向链表中第一个结点的指针域(nextarc)。 图中的所有头结点以顺序结构存储。 在图 7.10 中分别给出邻接表表结点的结构示图(a)和头结点的结构示图(b)。例如，图 7.11 分别给出有向图 G1 和无向图 G2 的一种邻接表表示结构。由于图中顶点的排列次序可以不同，每个顶点的邻接点的排列顺序也可以不同，所以， 一个图的邻接表表示不唯一。 用邻接表表示具有 n 个顶点和 e 条边的无向图时， 需要一个由 n 个元素组成的顺序表 （表 头结点表）和由 2e 个结点组成的 n 个单链表。而表示 n 个顶点和 e 条弧的有向图时，需要一 个由 n 个元素组成的顺序表和由 e 个结点组成的 n 个单链表。当图中边（或弧）的数目远远少 于图的顶点数目时，邻接表所需的存储空间要比邻接矩阵所需的少。 2．逆邻接表-.176.-第 7 章 图结构在图 G 的邻接表中，顶点 v 的相邻元素可以通过遍历该顶点对应的单链表求得，设该链 表中结点的个数为 k 那么，G 为无向图时 k 表示 v 的度，G 为有向图时 k 表示 v 的出度。如果 求顶点 v 的入度，则需要遍历邻接表中的所有单链表，统计与 v 的序号相同的结点个数。这 样处理很不方便，为此，仿照邻接表，建立一个逆邻接表，即对每个顶点 v 建立一个单链表， 把所有邻接于 v 的顶点链接在一起，此时该单链表的长度即为 v 的入度。 例如，图 7.11(a)所示的有向图可用逆邻接表表示为图 7.12。3．邻接表的存储表示与实现 (1)邻接表存储结构的类型定义 定义单链表结点类型 ArcNode： struct ArcNode{ int adjvex,ArcNode*}; 定义链表头结点结构类型 VexNode： struct VexNode{VTArcNode*}; 定义邻接表存储结构的类型 ALGraph： struct ALGraph{ VexNode* //定义头结点数组指针 vertices int vexnum, //顶点数 vexnum 和边或弧数 arcnum GK //图的种类标志 kind }; (2)查找图中顶点位置的操作 函数的功能是，返回顶点 u 在图 G 中的位置，查找失败返回 0 值。 int LocateVex_AL(ALGraph G,VType u) { for(i=0;i&G.i++) if(G.vertices[i].data==u) if(i&G.vexnum)return(i+1); else return(0); } (3)邻接表的建立操作 函数的功能是，根据图 G 的种类标志 kind 建立 G 的邻接表表示的存储结构。 #include&iostream.h& void CreateGraph_AL(ALGraph& G,GKind kind) { int i,j,k;-.177.-第 7 章 图结构VType u,v; ArcNode* pr,*pr1; G.kind= cout&&&输入顶点数和边(弧)数 vexnum arcnum:&; cin&&G.vexnum&&G. G.vertices=new VexNode[G.vexnum];//为顶点数组分配内存空间cout&&&按某种顺序输入&&&G.vexnum&&&个顶点的值:\n&; for(i=0;i&G.i++) { G.vertices[i].flag=0; //flag=0 表示该顶点未被访问 cin&&G.vertices[i]. //输入所有顶点的信息到 vex 中 G.vertices[i].nextarc=NULL; //设定初始的单链表为空 } if(G.kind==DG||G.kind==UDG) cout&&&输入图中&&&G.arcnum&&&条边(弧)的信息 u v:\n&; else cout&&&输入图中&&&G.arcnum&&&条边(弧)和权的信息 u v w:\n&; for(k=0;k&G.k++) //输入所有边或弧的相邻顶点信息 { do{ cin&&u&&v;} while(!((i=LocateVex_AL(G,u))&&(j=LocateVex_AL(G,v)))); i--,j--; //i,j 从位置值转换为下标值 pr=new ArcN //动态分配单链表结点 pr pr-&adjvex=j; pr-&weight=0; if(G.kind==DN||G.kind==UDN)cin&&pr-& //输入对应边（弧）的权值 pr-&nextarc=G.vertices[i]. //将结点 pr 插入到第 i 个链表的首部 G.vertices[i].nextarc= if(G.kind==UDG||G.kind==UDN) //对于无向图(或网)将结点 pr1 插入到第 j 个链表的首部 { pr1=new ArcN //动态分配单链表结点 pr1 pr1-&adjvex=i; pr1-&weight=pr-& pr1-&nextarc=G.vertices[j]. G.vertices[j].nextarc=pr1; //将结点 pr1 插入到第 j 个链表的首部 }//end switch }//end for } (4)显示输出邻接矩阵的操作 函数功能是，显示输出图 G 的邻接链表中的所有信息。 void DisplyAL(ALGraph G)//显示邻接矩阵 G {-.178.-第 7 章 图结构ArcNode* for(i=0;i&G.i++) { p=G.vertices[i]. cout&&i&&& (&&&G.vertices[i].data&&&): &; while(p) { if(G.kind==DG||G.kind==UDG) //对于图仅输出顶点的下标值 cout&&'['&&p-&adjvex&&&] &; else //对于网要输出下标与对应的权的值 cout&&'['&&p-&adjvex&&','&&p-&weight&&&] &; p=p-& } cout&& }//end for } (5)演示程序主函数 程序中分别建立有向图 G1、无向图 G2、有向网 G3 和无向网 G4 的邻接表，并显示输出 所建立的每个邻接表的数据信息。 void main() { ALGraph G1,G2,G3,G4; GKind gk1=DG,gk2=UDG,gk3=DN,gk4=UDN; cout&&&建立一个有向图的邻接表 G1:\n&; CreateGraph_AL(G1,gk1); cout&&&建立一个无向图的邻接表 G2:\n&; CreateGraph_AL(G2,gk2); cout&&&有向图 G1 的邻接表为:\n&; DisplyAL(G1); cout&&&无向图 G2 的邻接表为:\n&; DisplyAL(G2); cout&&&***************************************\n&; cout&&&建立一个有向网的邻接表 G3:\n&; CreateGraph_AL(G3,gk3); cout&&&建立一个无向网的邻接表 G4:\n&; CreateGraph_AL(G4,gk4); cout&&&有向网 G3 的邻接表为:\n&; DisplyAL(G3); cout&&&无向网 G4 的邻接表为:\n&; DisplyAL(G4); } 程序运行演示结果为：建立一个有向图的邻接表 G1: 输入顶点数和边(弧)数 vexnum arcnum:6 8L-.179.-第 7 章 图结构按某种顺序输入 6 个顶点的值: 1 2 3 4 5 6L 输入图中 8 条边(弧)的信息 u v: 1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5L 建立一个无向图的邻接表 G2: 输入顶点数和边(弧)数 vexnum arcnum:6 7L 按某种顺序输入 6 个顶点的值: 1 2 3 4 5 6L 输入图中 7 条边(弧)的信息 u v: 1 2 1 4 2 3 2 6 5 3 5 6 5 4L 有向图 G1 的邻接表为: 0 (1): [3] [1] 1 (2): 2 (3): [5] [0] 3 (4): [2] 4 (5): [3] 5 (6): [4] [0] 无向图 G2 的邻接表为: 0 (1): [3] [1] 1 (2): [5] [2] [0] 2 (3): [4] [1] 3 (4): [4] [0] 4 (5): [3] [5] [2] 5 (6): [4] [1] *************************************** 建立一个有向网的邻接表 G3: 输入顶点数和边(弧)数 vexnum arcnum:4 4L 按某种顺序输入 4 个顶点的值: 1 2 3 4L 输入图中 4 条边(弧)和权的信息 u v w: 1 2 7 1 3 1 3 4 5 4 1 9L 建立一个无向网的邻接表 G4: 输入顶点数和边(弧)数 vexnum arcnum:5 5L 按某种顺序输入 5 个顶点的值: 1 2 3 4 5L 输入图中 5 条边(弧)和权的信息 u v w: 1 2 9 4 1 8 4 2 3 4 5 1 3 5 12 L 有向网 G3 的邻接表为: 0 (1): [2,1] [1,7] 1 (2): 2 (3): [3,5] 3 (4): [0,9] 无向网 G4 的邻接表为: 0 (1): [3,8] [1,9] 1 (2): [3,3] [0,9] 2 (3): [4,12] 3 (4): [4,1] [1,3] [0,8] 4 (5): [2,12] [3,1]说明： （1） 程序演示中建立的是图 7.1、 图 7.3 中 4 个图的一种邻接表表示： G1.vertices、 G2.vertices、 G3.vertices 和 G4.vertices。 （2）在程序显示的结果中，第一列为顶点的下标，第二列为图中所有顶点的值。对于图， 单链表中的每一项表示该顶点的邻接点的下标；对于网，单链表中的每一项表示该顶点的邻 接点的下标值和相应边（弧）的权值。 （3）在建立邻接表时，由于输入的是顶点信息，所以要先通过查找求得该顶点在图中的位 置，再将相应结点插入到对应单链表的首部，所以，该操作的时间复杂度为 O(n*e)。7.2.3 有向图的十字链表表示法十字链表是有向图的另一种链式存储结构，该方法是将有向图的邻接表和逆邻接表结合 起来得到的一种链表。 1．十字链表的定义 类似邻接表，在十字链表中包含链表的头结点和弧结点两种类型的结点，图 7.13 给出十 字链结点结构的示图。其中，头结点包含顶点信息域 (data) 、指向以该顶点为弧头的第一个弧结点的指针域 (firstin)、 指向以该顶点为弧尾的第一个弧结点的指针域(firstout)， 表的所有头结点以顺序存储。 弧结点包含表示弧尾顶点下标的尾域(tailvex)、表示弧头顶点下标的头域(headvex)、指向弧头 相同的下一条弧的指针域(hlink)、指向弧尾相同的下一条弧的指针域(tlink)、弧的信息（如权-.180.-第 7 章 图结构值）域(info)。 例如，图 7.14 给出有向图的一种十字链表表示。如果将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的十 字链表存储结构。在有向图的十字链表表示中，链表的头结点之间是顺序存储结构，弧结点 所在的链表是非循环链表，结点之间的相对位置自然形成，不一定按顶点序列号有序。由此 可见，有向图的十字链表表示方式是不唯一的。 2．十字链表的存储表示与实现 (1)十字链表存储结构的类型定义 下面分别给出十字链弧结点(ArcBox)、 顶点结点(OLVexNode)、 十字链表(OLGraph)的类型 定义。 struct ArcBox{ //弧结点的结构定义 int tailvex, //定义弧尾和弧头顶点的位置 ArcBox *hlink,* //弧头相同、弧尾相同的弧的链域 //定义有向网中弧的权值 }; struct OLVexNode{ //顶点结点结构定义 VT //顶点信息 ArcBox *firstin,* //分别指向顶点的第一条入弧和出弧 }; struct OLGraph{ //定义十字链表类型 OLVexNode * //链表头结点数组指针 int vexnum, //有向图的顶点数和弧数 GK }; (2)十字链表的查找操作 函数 int LocateVex_OLG(OLGraph G,VType u) 返回顶点 u 在图 G 中的位置， 如果查找失 败则返回 0 值。 int LocateVex_OLG(OLGraph G,VType u) { for(i=0;i&G.i++) if(G.xlist[i].data==u) if(i&G.vexnum)return(i+1);-.181.-第 7 章 图结构else return(0); } (3)建立十字链表的算法实现 函数 void CreateGraph_OLG(OLGraph& G,GKind kind)根据图的类型 kind 建立一个有向图 或有向网的十字链表 G。 void CreateGraph_OLG(OLGraph& G,GKind kind) { int i,j,k; VType u,v; ArcBox* G.kind= cout&&&输入顶点数和边(弧)数 vexnum arcnum:&; cin&&G.vexnum&&G. G.xlist=new OLVexNode[G.vexnum]; //为顶点数组分配内存空间 cout&&&按某种顺序输入&&&G.vexnum&&&个顶点的值:\n&; for(i=0;i&G.i++) { cin&&G.xlist[i]. //输入所有顶点的信息到 data 中 G.xlist[i].firstin=G.xlist[i].firstout=NULL; //设定初始的单链表为空 } if(G.kind==DG)cout&&&输入图中&&&G.arcnum&&&条弧的信息 u v:\n&; else cout&&&输入图中&&&G.arcnum&&&条弧和权的信息 u v w:\n&; for(k=0;k&G.k++) { do{ cin&&u&&v; } while(!((i=LocateVex_OLG(G,u))&&(j=LocateVex_OLG(G,v)))); pr=new ArcB //动态分配弧存储空间 pr-&tailvex=--i; //i 从位置值转换为下标值 pr-&headvex=--j; //j 从位置值转换为下标值 if(G.kind==DN)cin&&pr-& pr-&hlink=G.xlist[j]. //将输入的弧插入到相应链表的首部 G.xlist[j].firstin= pr-&tlink=G.xlist[i]. G.xlist[i].firstout= }//end for } (4)显示十字链表信息的操作 函数 void DisplyOLG(OLGraph G)分别按邻接表和逆邻接表方式显示当前十字链表 G 的信 息。 void DisplyOLG(OLGraph G) { ArcBox*-.182.-第 7 章 图结构cout&&&按邻接表显示结果为：\n&; for(i=0;i&G.i++) { p=G.xlist[i]. cout&&i&&& (&&&G.xlist[i].data&&&): &; while(p) { cout&&'['&&p-&tailvex&&' '&&p-& if(G.kind==DN)cout&&' '&&p-& cout&&&] &; p=p-& } cout&& }//end for cout&&&按逆邻接表显示结果为：\n&; for(i=0;i&G.i++) { p=G.xlist[i]. cout&&i&&& (&&&G.xlist[i].data&&&): &; while(p) { cout&&'['&&p-&tailvex&&' '&&p-& if(G.kind==DN)cout&&' '&&p-& cout&&&] &; p=p-& } cout&& }//end for } (5)程序演示主程序代码 程序中分别建立一个有向图 G1 和一个有向网 G2 的十字链表，并按邻接表和逆邻接表两 种形式显示所建立的的十字链表的内容。 void main() { OLGraph G1,G2; GKind gk1=DG,gk2=DN; cout&&&建立一个有向图的十字链表 G1:\n&; CreateGraph_OLG(G1,gk1); cout&&&建立一个有向网的十字链表 G2:\n&; CreateGraph_OLG(G2,gk2); cout&&&有向图 G1 的信息为:\n&; DisplyOLG(G1); cout&&&有向网 G2 的信息为:\n&; DisplyOLG(G2); }程序运行演示结构为：-.183.-第 7 章 图结构建立一个有向图的十字链表 G1: 输入顶点数和边(弧)数 vexnum arcnum:4 7L 按某种顺序输入 4 个顶点的值: 1 2 3 4L 输入图中 7 条弧的信息 u v: 1 2 1 3 3 1 3 4 4 1 4 2 4 3L 建立一个有向网的十字链表 G2: 输入顶点数和边(弧)数 vexnum arcnum:4 7L 按某种顺序输入 4 个顶点的值: 1 2 3 4L 输入图中 7 条弧和权的信息 u v w: 128 135 312 344 416 427 433 L 有向图 G1 的信息为: 按邻接表显示结果为： 0 (1): [0 2] [0 1] 1 (2): 2 (3): [2 3] [2 0] 3 (4): [3 2] [3 1] [3 0] 按逆邻接表显示结果为： 0 (1): [3 0] [2 0] 1 (2): [3 1] [0 1] 2 (3): [3 2] [0 2] 3 (4): [2 3] 有向网 G2 的信息为: 按邻接表显示结果为： 0 (1): [0 2 5] [0 1 8] 1 (2): 2 (3): [2 3 4] [2 0 2] 3 (4): [3 2 3] [3 1 7] [3 0 6] 按逆邻接表显示结果为： 0 (1): [3 0 6] [2 0 2] 1 (2): [3 1 7] [0 1 8] 2 (3): [3 2 3] [0 2 5] 3 (4): [2 3 4]说明： （1）在程序显示的结果中，第一列、第二列分别为顶点位置的下标和顶点的值。对于图， 单链表中的每一项表示该顶点及其邻接点的下标；对于网，还要显示相应弧的权值。 （2）程序演示中所建立的是图 7.15 中有向图(a)和有向网(b)的十字链表的一种表示。（3）从存储结构可以看出，在十字链表中很容易算出一个顶点的出度和入度，并且建立十 字链表的时间复杂度与建立邻接表的时间复杂度相同，均为 O(n*e)。所以在有向图的应用中， 十字链表是一个很有用的工具。7.2.4 无向图的邻接多重表表示法在无向图的邻接表表示中，每一条边(v,w)均出现两次，即在顶点 v 的单链表中有顶点 v、 w 构成的边结点，同时在顶点 w 的单链表中有顶点 w、v 构成的边结点。这样，在对边进行搜 索的有关问题中，同一条边出现两次显然会带来一些不便；同时，当图中的边数较大时明显 增加了内存空间的占用量。为此，下面给出无向图的邻接多重链表表示法。 1．邻接多重表的定义 在邻接多重表中包含链表的头结点和链表中的边结点两种类型的结点，图 7.16 给出邻接 多重表中头结点和边结点结构的结构示图。其中，头结点包含顶点信息域 (data) 、指向依附于该顶点的第一条边结点的指针域-.184.-第 7 章 图结构(firstedge)。边结点包含判断该边是否被扫描过的标志域(mark)、该边依附的第一个顶点位置域 (ivex)、边依附的第二个顶点位置域(jvex)、指向下一条依附于 ivex 的边的指针域(ilink)、指向 下一条依附于 jvex 的边的指针域(jlink)、边的信息（比如权值）域(info)。 例如，图 7.17 给出无向图的一种邻接多重表表示。在邻接多重表中，所有依附于同一顶点的边链接在一个链表中，由于一条边依附于两个 顶点，所以每个边结点同时出现在两个链表中。所以，无向图的邻接多重表中边结点的个数 是其邻接表表示中边结点个数的一半。邻接多重链表中，表的头结点之间是顺序存储结构， 边结点所在的链表是非循环链表，结点之间的相对位置也是自然形成的，不一定按顶点序列 号有序。所以，无向图的邻接多重表表示方式是不唯一的。 2．邻接多重表的存储表示与实现 (1)邻接多重表存储结构的类型定义 下面分别给出边结点(EBox)、顶点结点(VexBox)、邻接多重链表(AMLGraph)的类型定义。 struct EBox{ //边结点的结构定义 //访问标志域 int ivex, //边依附的两个顶点的位置 EBox *ilink,* //指向依附两个顶点的下一条边的指针域 //边的相关信息（如权值）域 }; struct VexBox{ //顶点结点结构定义 VT //顶点信息 EBox * //指向第一条依附该顶点的边 }; struct AMLGraph{ //定义邻接多重链表类型 VexBox* //链表头结点数组指针 int vexnum, //无向图的顶点数和边数 GK }; (2)邻接多重链表的查找操作 函数 int LocateVex_AMLG(AMLGraph G,VType u)返回顶点 u 在图 G 中的位置，如果查找 失败则返回 0 值。-.185.-第 7 章 图结构int LocateVex_AMLG(AMLGraph G,VType u) { for(i=0;i&G.i++) if(G.xlist[i].data==u) if(i&G.vexnum)return(i+1); else return(0); } (3)建立邻接多重链表的算法实现 函数 void CreateGraph_AMLG(AMLGraph& G,GKind kind)根据图的类型(kind)建立一个无 向图或无向网的邻接多重链表(G)。 void CreateGraph_AMLG(AMLGraph& G,GKind kind) { int i,j,k; VType u,v; EBox* G.kind= cout&&&输入顶点数和边数 vexnum edgenum:&; cin&&G.vexnum&&G. G.xlist=new VexBox[G.vexnum]; //为顶点数组分配内存空间 cout&&&按某种顺序输入&&&G.vexnum&&&个顶点的值:\n&; for(i=0;i&G.i++) { cin&&G.xlist[i]. //输入所有顶点的信息到 data 中 G.xlist[i].firsedge=NULL; //设定初始的单链表为空 } if(G.kind==DG) cout&&&输入图中&&&G.edgenum&&&条边的信息 u v:\n&; else cout&&&输入图中&&&G.edgenum&&&条边和权的信息 u v w:\n&; for(k=0;k&G.k++) { do{ cin&&u&&v; } while(!((i=LocateVex_AMLG(G,u))&&(j=LocateVex_AMLG(G,v)))); pr=new EB //动态分配边的存储空间 pr-&ivex=--i; //i 从位置值转换为下标值 pr-&jvex=--j; //j 从位置值转换为下标值 if(G.kind==DN)cin&&pr-& pr-&ilink=G.xlist[i]. //将输入的边插入到相应链表的首部 G.xlist[i].firsedge= pr-&jlink=G.xlist[j]. G.xlist[j].firsedge= }//end for } (4)按邻接表方式显示当前邻接多重链表的信息-.186.-第 7 章 图结构函数 void DisplyAMLG(AMLGraph G)按邻接表的方式显示当前邻接多重链表表示的无向 图 G 的相关信息。 void DisplyAMLG(AMLGraph G) { EBox* cout&&&按邻接表显示结果为：\n&; for(i=0;i&G.i++) { p=G.xlist[i]. cout&&i&&& (&&&G.xlist[i].data&&&): &; while(p) //输出边的信息 { if(p-&ivex==i) cout&&'['&&p-&ivex&&' '&&p-& else cout&&'['&&p-&jvex&&' '&&p-& if(G.kind==DN)cout&&' '&&p-& cout&&&] &; if(p-&ivex==i) p=p-& //指针指向下一个边结点 else p=p-& } cout&& }//end for } (5)程序演示主程序代码 程序中分别建立一个无向图(G1)和一个无向网(G2)的邻接多重链表， 并按邻接表的形式显 示所建立的的邻接多重链表的内容。 void main() { AMLGraph G1,G2; GKind gk1=DG,gk2=DN; cout&&&建立一个无向图的邻接多重链表 G1:\n&; CreateGraph_AMLG(G1,gk1); cout&&&建立一个无向网的邻接多重链表 G2:\n&; CreateGraph_AMLG(G2,gk2); cout&&&无向图 G1 的信息为:\n&; DisplyAMLG(G1); cout&&&无向网 G2 的信息为:\n&; DisplyAMLG(G2); }程序运行演示结果为：建立一个无向图的邻接多重链表 G1: 输入顶点数和边数 vexnum edgenum:4 5L 按某种顺序输入 4 个顶点的值: 1 2 3 4L 输入图中 5 条边的信息 u v: 1 2 1 3 1 4 2 3 2 4L 建立一个无向网的邻接多重链表 G2: 输入顶点数和边数 vexnum edgenum:4 5L-.187.-第 7 章 图结构按某种顺序输入 4 个顶点的值: 1 2 3 4L 输入图中 5 条边和权的信息 u v w: 1 2 3 1 3 6 1 4 4 2 3 5 2 4 8L 无向图 G1 的信息为: 按邻接表显示结果为： 0 (1): [0 3] [0 2] [0 1] 1 (2): [1 3] [1 2] [1 0] 2 (3): [2 1] [2 0] 3 (4): [3 1] [3 0] 无向网 G2 的信息为: 按邻接表显示结果为： 0 (1): [0 3 4] [0 2 6] [0 1 3] 1 (2): [1 3 8] [1 2 5] [1 0 3] 2 (3): [2 1 5] [2 0 6] 3 (4): [3 1 8] [3 0 4]说明： （1）程序演示中所建立的是图 7.18 中无向图(a)和无向网(b)的邻接多重链表的一种表示。（2）从存储结构可以看出，在邻接多重结构存储的链表中很容易算出一个顶点的度，并且 建立邻接多重链表的时间复杂度与建立邻接表的时间复杂度相同，所以在无向图（或网）的 应用中，常常用邻接多重链表作为存储结构。7.3 图的遍历从图中某一顶点出发，访问图中其余各顶点，而且每个顶点仅被访问一次的过程称为 图 的遍历。图的遍历算法是图的诸多应用中的基础，例如求解图的连通性、生成树、拓扑排序、 关键路径等问题中都是以图的遍历算法为基础。 图的遍历比树的遍历要复杂得多，因为图中任意两个顶点之间都可能有边（或弧）存在， 所以在访问了某个顶点之后，可能沿着某个路径又回到该顶点上，由此可能导致某个顶点在 遍历的过程中被访问多次。为了保证在遍历过程中每个顶点仅被访问一次，必须记下已访问 过的顶点。通常需要设立一个一维数组 visited[]，其中每个元素对应图中某个顶点被访问的次 数，遍历前它们的值均为 0，表示相应的顶点未被访问过，一旦该顶点被访问则数组 visited 中相应的元素值变为 1。为了方便起见，我们在图的邻接矩阵和邻接表存储的顶点序列 vexs[] （邻接矩阵）和 vertices[]（邻接表）中均增设了用于表示该顶点是否被访问过的标志域 flag。 图的遍历算法通常有深度优先搜索 (depth first search) 和广度度优先搜索 (breadth first search)两种。7.3.1 图的深度优先搜索1．深度优先遍历的定义 图的深度优先搜索类似于树的先根遍历，是树的先根遍历的推广。设初始状态是图中的 所有顶点均未被访问。深度优先遍历过程为： 首先访问指定的起始顶点 u，然后选取与 u 邻接的未被访问的任一顶点 v 访问之，再选取 与 v 邻接的未被访问的任一顶点 w 访问之。重复进行以上访问过程，当到达一个所有邻接顶-.188.-第 7 章 图结构点都被访问过的顶点时，则依次退回到最近被访问过的顶点。若它还有邻接的顶点未被访问 过，则从这些未被访问过的顶点中任意选取一个顶点，重复上述过程，直到所有的顶点都被 访问过为止。 说明： (1) 图的深度优先搜索法的遍历过程是一个递归过程； (2) 根据深度优先搜索的定义可知，同一个图，从同一个顶点开始，可以得到多种不同的 深度优先遍历序列。所以，图的深度优先遍历序列不唯一。 例如： (1) 图 7.18 所示的无向图，从顶点 1 开始的深度优先遍历序列有以下 4 种： 1) 1、2、3、4；2) 1、2、4、3；3) 1、4、2、3；4) 1、3、2、4。 (2) 图 7.11(b)所示的无向图，从顶点 v1 开始的深度优先遍历序列有以下 5 种： 1) v1，v2，v5，v3，v4；2) v1，v2，v5，v4，v3；3) v1，v3，v4，v5，v2； 4) v1，v3，v5，v2，v4；5) v1，v3，v5，v4，v2。 (3) 图 7.15 所示的有向图，从顶点 v1 开始的深度优先遍历序列有以下 2 种： 1) v1，v2，v3，v4； 2) v1，v3，v4，v2。 (4) 图 7.19 所示的无向图， 从顶点 1 开始， 按顶点编号递增顺序进行深度优先遍历的序列 为： 1、2、4、8、5、6、3、7。 从顶点 1 开始，按顶点编号递减顺序进行深度优先遍历的序列为： 1、3、7、8、6、5、2、4。2．深度优先遍历的算法实现 深度优先算法，在遍历的过程中需要访问邻接表 G 的标志数组 G.vertices[v].flag，顶点一 旦被访问则其相应的标志由 0 修改为 1。 (1)对连通分量的深度优先遍历 函数 void DFS_ALG(ALGraph &G,int v)的功能是，对以邻接表方式存储的图 G，从顶点编 号为 v 的顶点开始，用递归的方式，深度优先遍历该顶点所在的连通分量。 void DFS_ALG(ALGraph &G,int v) { ArcNode* cout&&G.vertices[v].data&&' '; //访问该结点 G.vertices[v].flag=1; //修改访问标志 for(p=G.vertices[v].p;p=p-&nextarc) //进入下一层 { w=p-&-.189.-第 7 章 图结构if(!G.vertices[w].flag)DFS_ALG(G,w); } } (2)对图的深度优先遍历 函数 void DFSTraverse_ALG(ALGraph G)的功能是，通过重复调用函数 DFS_ALG(G,v)实 现对邻接表 G 的深度优先遍历。 void DFSTraverse_ALG(ALGraph G) { for(v=0;v&G.v++) if(!G.vertices[v].flag)DFS_ALG(G,v); cout&& } (3)主函数演示程序 主函数首先建立有向图 G1 和无向图 G2 的邻接表，再分别对其进行深度优先遍历并显示 输出邻接表和遍历序列。 void main() { ALGraph G1,G2; GKind gk1=DG,gk2=UDG; cout&&&建立一个有向图的邻接表 G1:\n&; CreateGraph_AL(G1,gk1); cout&&&建立一个无向图的邻接表 G2:\n&; CreateGraph_AL(G2,gk2); cout&&&有向图 G1 的邻接表为:\n&; DisplyAL(G1); cout&&&有向图 G1 的深度优先遍历序列为:\n&; DFSTraverse_ALG(G1); cout&&&无向图 G2 的邻接表为:\n&; DisplyAL(G2); cout&&&无向图 G2 的深度优先遍历序列为:\n&; DFSTraverse_ALG(G2); }程序运行演示结果如下：建立一个有向图的邻接表 G1: 输入顶点数和边(弧)数 vexnum arcnum:6 10L 按某种顺序输入 6 个顶点的值: 1 2 3 4 5 6L 输入图中 10 条边(弧)的信息 u v: 14 12 35 32 45 42 52 51 65 6 3L 建立一个无向图的邻接表 G2: 输入顶点数和边(弧)数 vexnum arcnum:8 10L 按某种顺序输入 8 个顶点的值: 1 2 3 4 5 6 7 8L 输入图中 10 条边(弧)的信息 u v: 13 12 25 24 37 36 87 86 8 4L 有向图 G1 的邻接表为: 0 (1): [1] [3] 1 (2): 2 (3): [1] [4] 3 (4): [1] [4] 4 (5): [0] [1] 5 (6): [2] [4] 有向图 G1 的深度优先遍历序列为: 85 //通过递归调用实现深度优先遍历-.190.-第 7 章 图结构124536 无向图 G2 的邻接表为: 0 (1): [1] [2] 1 (2): [3] [4] [0] 2 (3): [5] [6] [0] 3 (4): [7] [1] 4 (5): [7] [1] 5 (6): [7] [2] 6 (7): [7] [2] 7 (8): [3] [4] [5] [6] 无向图 G2 的深度优先遍历序列为: 说明： （1）程序运行演示中建立的是图 7.8 所示的有向图和图 7.19 所示的无向图的一种邻接表表 示 G1 和 G2，并以邻接表中第一个顶点开始分别对其进行深度优先遍历，并显示输出遍历序 列。 （2）对同一个图，如果输入的顶点值序列的顺序不同或输入的边（或弧）的顺序不同，那 么创建的邻接表也不同，从而得到的深度优先遍历序列也不同。 （3）图的深度优先遍历的时间复杂度取决于图的存储结构。当以邻接矩阵作为图的存储结 构时的时间复杂度为 O(n2)，当以邻接表作为图的存储结构时的时间复杂度为 O(e+n)。7.3.2 图的广度优先搜索1．广度优先遍历的定义 图的广度优先搜索类似于树的层次遍历，也是图的一种普遍采用的遍历算法。设初始状 态是图中的所有顶点均未被访问。广度优先遍历过程如下： 首先访问指定的起始顶点 u，再按某种顺序依次访问 u 的所有未被访问过的邻接点序列： v1,v2,v3,…,vk；然后按照次序 v1,v2,v3,…,vk 逐个访问其中每个顶点的所有未被访问过的邻接 点（按某种顺序） ，继续以上过程，直到图中所有和初始顶点 u 有路径相通的顶点均被访问过 为止。如果图中还存在与初始顶点 u 不连通的顶点，则任选一个没被访问过的顶点做起点， 重复上述过程，直到图中所有的顶点均被访问过为止。 说明：根据广度优先搜索的定义可知，同一个图，从同一个顶点开始，可以得到多种不 同的广度优先遍历序列。所以，图的广度优先遍历序列不唯一。 例如： (1) 图 7.18 所示的无向图，从顶点 1 开始的广度优先遍历序列有以下 6 种： 1) 1、2、4、3； 2) 1、2、3、4； 3) 1、4、2、3； 4) 1、4、3、2； 5) 1、3、4、2； 6) 1、3、2、4。 (2) 图 7.15 所示的有向图，从顶点 v1 开始的广度优先遍历序列有以下 2 种： 1) v1，v2，v3，v4； 2) v1，v3，v2，v4。 (3) 图 7.19 所示的无向图， 从顶点 1 开始， 按顶点编号递增顺序进行广度优先遍历的序列 为： 1、2、3、4、5、6、7、8。 从顶点 1 开始，按顶点编号递减顺序进行广度优先遍历的序列为： 1、3、2、7、6、5、4、8。 2．广度优先遍历的算法实现 和深度优先算法类似， 在遍历的过程中也需要访问邻接表 G 的标志数组 G.vertices[v].flag， 另外还需要一个队列 Q 来存放已被访问的顶点的标号。在图的某个连通分量中，当访问了一-.191.-第 7 章 图结构个顶点后，该顶点的标号入队；然后，从队列头部取出一个顶点下标，依次访问该下标所对 应顶点的所有未被访问过的邻接点，并依次将各个访问过的邻接点的下标入队，直到队列为 空为止。 (1)遍历算法实现 函数 void BFSTraverse_ALG(ALGraph G)实现对邻接表表示的图 G 的广度优先遍历。 void BFSTraverse_ALG(ALGraph G) { int v,w,u,n=G. int* Q=new int[G.vexnum]; //定义顶点标号队列 Q int front=0,real=0; ArcNode* for(v=0;v&G.v++) { if(!G.vertices[v].flag) { G.vertices[v].flag=1; //修改标志 cout&&G.vertices[v].data&&' '; //访问该结点 Q[real++]=v; //顶点标号入队 real%=n; while(front!=real) //当队列 Q 不空 { w=Q[front++]; front%=n; //顶点标号出队 pr=G.vertices[w]. while(pr) { u=pr-& if(!G.vertices[u].flag) { G.vertices[u].flag=1; //修改标志 cout&&G.vertices[u].data&&' '; //访问该结点 Q[real++]=u; real%=n; //顶点标号入队 } pr=pr-& //进入下一个邻接点 }//end while }//end while }//end if }//end for cout&& } (2)主函数调用演示程序 主函数首先建立有向图 G1 和无向图 G2 的邻接表，再分别对其进行广度优先遍历并显示输 出邻接表和遍历序列。 void main() { ALGraph G1,G2;-.192.-第 7 章 图结构GKind gk1=DG,gk2=UDG; cout&&&建立一个有向图的邻接表 G1:\n&; CreateGraph_AL(G1,gk1); cout&&&建立一个无向图的邻接表 G2:\n&; CreateGraph_AL(G2,gk2); cout&&&有向图 G1 的邻接表为:\n&; DisplyAL(G1); cout&&&有向图 G1 的广度优先遍历序列为:\n&; BFSTraverse_ALG(G1); cout&&&无向图 G2 的邻接表为:\n&; DisplyAL(G2); cout&&&无向图 G2 的广度优先遍历序列为:\n&; BFSTraverse_ALG(G2); }程序运行演示结果如下：建立一个有向图的邻接表 G1: 输入顶点数和边(弧)数 vexnum arcnum:6 10L 按某种顺序输入 6 个顶点的值: 1 2 3 4 5 6L 输入图中 10 条边(弧)的信息 u v: 14 12 35 32 45 42 52 51 65 6 3L 建立一个无向图的邻接表 G2: 输入顶点数和边(弧)数 vexnum arcnum:8 10L 按某种顺序输入 8 个顶点的值: 1 2 3 4 5 6 7 8L 输入图中 10 条边(弧)的信息 u v: 13 12 25 24 37 36 87 86 85 8 4L 有向图 G1 的邻接表为: 0 (1): [1] [3] 1 (2): 2 (3): [1] [4] 3 (4): [1] [4] 4 (5): [0] [1] 5 (6): [2] [4] 有向图 G1 的广度优先遍历序列为: 124536 无向图 G2 的邻接表为: 0 (1): [1] [2] 1 (2): [3] [4] [0] 2 (3): [5] [6] [0] 3 (4): [7] [1] 4 (5): [7] [1] 5 (6): [7] [2] 6 (7): [7] [2] 7 (8): [3] [4] [5] [6] 无向图 G2 的广度优先遍历序列为: 说明： （1）程序运行演示中建立的是图 7.8 所示的有向图和图 7.19 所示的无向图的一种邻接表表 示：G1、G2。并分别对其进行广度优先遍历，显示输出遍历序列。广度优先算法的时间复杂 度与深度优先算法相同。 （2）程序以邻接表中第一个顶点开始对图进行广度优先遍历。如果输入的顶点值序列的顺 序不同或输入的边（或弧）的顺序不同，那么得到的广度优先遍历序列也不同。7.4 生成树和最小（代价）生成树利用图的遍历算法可以求解图的连通性问题，进而可以求得无向图的生成树或生成森林。7.4.1 生成树1．生成树的概念-.193.-第 7 章 图结构设 G=(V,E)是一个连通的无向图，则从图 G 中的任一顶点出发，可以访问到 G 的全部顶 点。在对 G 的遍历过程中，所经过的边集设为 T(G)，没有经过的边集设为 B(G)，显然有 T∪ B=E，且 T∩B=?。对于图 G1=(V,T)，由于 V(G1)=V(G)，E(G1) ? E(G)，所以 G1 是 G 的一个连 通子图，且 G1 中含有 G 的所有顶点。我们把连通图中的所有顶点加上遍历时经过的所有边所 构成的子图称为生成树。显然 G1 是 G 的生成树。 说明： (1) 由于具有 n 个顶点的连通图 G 中至少有 n-1 条边，而 G 的生成树中恰好有 n-1 条边， 所以生成树是连通图的一个极小连通子图。 (2) 若在生成树中任意加上一条边，则必然形成回路。 (3) 一个连通图的生成树不是唯一的，这是由于遍历图时选择的起点不同、遍历的算法不 同（深度优先或广度优先） 、结点排列次序不同，因而会产生不同的生成树。 例如，图 7.20 中给出无向图(a)的 4 种不同的生成树(b)。(4) 对于不连通的无向图，从任意顶点出发，不能访问到图的所有顶点，只能得到连通分 量的生成树。一个图的所有连通分量的生成树组成该图的生成森林。 2．生成树的算法实现 对于连通的无向图，由深度优先遍历得到的生成树称为 深度优先生成树；由广度优先遍 历得到的生成树称为广度优先生成树。下面给出深度优先生成树（或森林）的算法实现过程。 (1)二叉链表的结点结构 为了用树的孩子兄弟表示法来表示生成树（或森林） ，下面给出其二叉链表的结构定义。 typedef struct CSNode { VT CSNode *firstchild,* }*CST (2)生成树的算法实现 函数 void DFSTree(ALGraph &G,int v,CSTree& T)的功能是， 从结点 v 开始对无向连通图 G 进行深度优先遍历得到深度优先生成树 T。 void DFSTree(ALGraph &G,int v,CSTree& T) { ArcNode* CSTree q,s=T; int w,first=1; G.vertices[v].flag=1; for(p=G.vertices[v].p;p=p-&nextarc)-.194.-第 7 章 图结构{ w=p-& if(!G.vertices[w].flag) { q=new CSN //动态分配结点 q q-&data=G.vertices[w]. //为结点 q 赋值 q-&firstchild=q-&nextsibling=NULL; if(first){ first=0; T-&firstchild=q; } //w 是第一个 v 的未被访问的邻接点 else{ s-&nextsibling=q; s=q; } //w 是 v 的其它未被访问的邻接点 DFSTree(G,w,q); //从 w 出发深度优先遍历 G，建立子生成树 q }//end_if }//end_for } (3)生成森林的算法实现 函数 void DFSForest(ALGraph G,CSTree& T)的功能是，从无向图 G 的第一个结点（按邻 接表中的结点顺序）开始，对 G 进行深度优先遍历得到深度优先生成森林（或树）T。 void DFSForest(ALGraph G,CSTree& T) { CSTree p,q; T=NULL; for(v=0;v&G.v++)G.vertices[v].flag=0; //初始化结点访问标志 for(v=0;v&G.v++) if(G.vertices[v].flag==0) { p=new CSN //动态分配结点 p p-&data=G.vertices[v]. //为结点 p 赋值 p-&firstchild=p-&nextsibling=NULL; if(!T)T=q=p; //v 是第一棵生成树的根 else{ q-&nextsibling=p; q=p;} //v 是其它生成树的根 DFSTree(G,v,p); //建立以 p 为根的生成树 } } 显然，该算法的时间复杂度与深度优先遍历算法的时间复杂度相同。7.4.2 最小（代价）生成树1．最小生成树的概念 对于无向网，因为它的边是带有权值的，而一个图的生成树是不唯一的，那么，就产生 了这样一个问题：如何找到一个各边的权值总和最小的生成树，这种生成树称为最小（代价） 生成树。最小生成树问题在实际应用中很有意义，比如，要在 n 个城市之间建立通信联络网， 最多有 n(n-1)/2 条路线，而连通这 n 个城市仅需要其中的 n-1 条路线（图的生成树）即可，由 于每对城市之间的距离不一样，铺设线路所花费的经济价格也不一同，此时，自然会考虑到-.195.-第 7 章 图结构如何在最节省经费（最小代价）的前提下建立通信网。 例如，图 7.21(b)是图 7.21(a)的最小生成树。常用的最小代价生成树算法有两种，即普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。这 两种算法都用了最小生成树的 MST 性质，即：设 N=(V,VR)是一个连通网，U 是顶点集 V 的一 个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中 u∈U，v∈V-U，则必有一棵包 含边(u,v)的最小生成树。 2．普里姆(Prim)算法 (1)普利姆算法思想 设 N=(V,VR)是一个连通网，TE 是 V 上最小生成树边的集合。普里姆（ Prim）算法从 U={u0}(u0∈V)，TE ={}开始。重复执行如下操作： 在所有 u∈U，v∈V-U 的边(u,v)∈VR 中找一条代价最小的边(u0,v0)并入集合 TE，同时 v0 并入 U，直至 U=V 为止。此时 TE 中必有 n-1 条边，则 T=(U,TE)为网 N=(V,VR)的最小生成树。 例如，对于图 7.21(a)所示的网，从顶点 1 开始，按照普里姆算法求最小生成树的过程， 可以由图 7.22(a)到图 7.22(f)表示。为了便于普里姆算法的实现，还需要附设一个数组 closedge[]，用以记录从 U 到 V-U 具有 最小代价的边。对每个顶点 vi∈V-U，在数组中存在相应的元素 closedge[i-1]，它包含两个域： 一个是 adjvex 域，用于存储该边所依附的在 U 中的点；另一个是 lowcost 域，用于存储该边-.196.-第 7 章 图结构上的权值。 lowcost 域的具体含义为：vi ? U ? ?1 ? closedge[i ? 1].low cos t ? ? 0 vi 与U不关联 ?? 0 v 到U的最小权值 ? i图 7.23 给出利用普里姆算法在图 7.22 所示的最小生成树的构造过程中， 辅助数组 closedge[] 中各个分量值的具体变化情况。图中第一行内的虚线框表示选中顶点 4 到 U 中，边(1,4)的权 值为 1；图中第二行中 closedge 为选入顶点 1、4 以后 U 到 V-U 的最短距离，其虚线框表示选 中顶点 2 到 U 中，边(1,2)的权值为 2；第三行中 closedge 为选入顶点 1、2、4 以后 U 到 V-U 的最短距离，其虚线框表示选中顶点 3 到 U 中，边(4,3)的权值为 2；以此类推，直到全部顶点 均被选入为止。(2)普利姆算法程序实现 定义辅助数组类型 CloseDge struct CloseDge{VT}; (1) 函数 void MiniTree_Prim(MGraph G,VType u)的功能是，对于邻接矩阵存储的网 G，从 顶点 u 开始，用普里姆算法构造一棵最小代价生成树，并输出该树的结点和边的权值。 void MiniTree_Prim(MGraph G,VType u) { int i,j,k,min, CloseDge *closedge=new CloseDge[G.vexnum]; if(!(k=LocateVex_MG(G,u))) k--; //将 k 转换为顶点 u 的下标-.197.-第 7 章 图结构for(max=G.arcs[0],i=0;i&G.i++) //求最大权值 max for(j=0;j&G.j++) if(max&G.arcs[i*G.vexnum+j]) max=G.arcs[i*G.vexnum+j]; for(j=0;j&G.j++) //初始化数组 closedge 为顶点 u 到所有顶点的距离 { closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k*G.vexnum+j]; } closedge[k].lowcost=-1; //初始顶点 k 并入 U cout&&'['&&closedge[k].adjvex&&']'; for(i=0;i&G.vexnum-1;i++) //选择其余 G.vexnum-1 个点 { min=closedge[i]. k=i; if(min&=0)min= for(j=0;j&G.j++) //查找 U 到 V-U 中权值最小的顶点下标 k if(closedge[j].lowcost&0 && closedge[j].lowcost&min) { min=closedge[j]. k=j; } cout&&'['&&closedge[k].adjvex&&','&&closedge[k].lowcost&&','&&G.vexs[k].vex&&']'; closedge[k].lowcost=-1; //顶点 k 并入 U for(j=0;j&G.j++) //修改 U 到 V-U 中各点的最短距离 { if(closedge[j].lowcost==-1) if(G.arcs[k*G.vexnum+j]&& (!closedge[j].lowcost||G.arcs[k*G.vexnum+j]&closedge[j].lowcost)) { closedge[j].lowcost=G.arcs[k*G.vexnum+j]; //取最小权值相应顶点的信息 closedge[j].adjvex=G.vexs[k]. } } } cout&& } (2) 主函数首先建立一个无向网的邻接矩阵 G，并显示输出该矩阵，接着从 4 号顶点开始 构造一棵最小生成树并显示输出该树的顶点和所对应的边的权值。 void main() { MGraph G; GKind gk=UDN; cout&&&建立一个无向网的邻接矩阵 G:\n&; CreateGraph_MG(G,gk); cout&&&无向网 G 的邻接矩阵为:\n&; DisplyMG(G); cout&&&无向网 G 的最小生成树为:\n&; VType u=G.vexs[3].-.198.-第 7 章 图结构MiniTree_Prim(G,u); } 程序演示结果为：建立一个无向网的邻接矩阵 G: 输入顶点数 vexnum 和弧数 arcnum:5 6L 按某种顺序输入 5 个顶点的值: 1 2 3 4 5L 输入图中 6 条边(弧)和权的信息 u v w: 1 2 10 1 4 12 2 3 5 2 5 18 3 4 1 3 5 8 L 无向网 G 的邻接矩阵为: 0 10 0 12 0 10 0 5 0 18
1 0 0 0 18 8 0 0 无向网 G 的最小生成树为: [4][4,1,3][3,5,2][3,8,5][2,10,1]说明： （1）在输出结果的最后一行中，第一项[4]为起始顶点的值，以后每一项为[顶点 1,权值,顶 点 2]。程序运行结果为图 7.24 所示的无向网(a)，从顶点 4 开始，由普里姆(prim)算法得到的 最小代价生成树(b)。（2）普里姆(prim)算法的时间复杂度与顶点数 n 有关而与边的个数无关，其时间复杂度为 O(n2)。所以，该算法适用于边数较多的情况。 3．克鲁斯卡尔(Kruskal)算法 (1)克鲁斯卡尔算法思想 克鲁斯卡尔算法的策略是：按照边的权值不减的顺序，依次考察每条边。如果该边和已 选的边不构成回路，则选择该边，否则去掉该边。重复执行以上过程直到构造出生成树为止。 设 N=(V,VR)是一个连通网，令最小生成树 T 的初始状态为只有 n 个顶点而无边的非连通 图 T=(V,{})，T 中每个顶点自成一个连通分量。那么，构造最小生成树的过程为：在 VR 中选 择权值最小的边，若该边依附的两个顶点分别落在 T 中的两个不同的连通分量上，则将该边 加入到 T 中；否则舍去此边寻找下一条最小代价边。依此类推，直到 T 为一个连通网为止， 此时的 T 即为最小生成树。 例如，对于图 7.21(a)所示的无向网，按照克鲁斯卡尔算法求最小生成树的过程，可以由 图 7.25(a)到图 7.25(f)表示。-.199.-第 7 章 图结构(2)克鲁斯卡尔算法的程序实现 该算法用到辅助数组 edge[]，其中按权值递增的顺序存放网中所有边的信息。数组元素的 类型 Edge 定义为：struct Edge{ VT int v1,v2;}; 其中，adjvex 为边(v1,v2)的权值。 (1) 函数 void EdgeSort(Edge* &edge,MGraph G)的功能是，将以邻接矩阵存储的无向网 G 中的所有边的信息按权值递增的顺序存储到数组 edge[]中 void EdgeSort(Edge* &edge,MGraph G) { int i,j,k,m,w,num=G. edge=new Edge[num]; //为 edge[]动态分配存储空间 E k=0; //k 表示 edge[]中元素个数，开始时 edge[]中有 0 个元素 for(i=0;i&G.i++) //将 G 中的所有边按权值递增的顺序插入到 edge[]中 for(j=0;j&i;j++) if(w=G.arcs[i*G.vexnum+j]) { arc.adjvex=w; arc.v1=i; arc.v2=j; for(m=k-1;m&=0;m--) { if(edge[m].adjvex&w) edge[m+1]=edge[m]; } edge[m+1]= k++; } } (2) 函数 void Findedge(ALGraph &G,int u,int v,int& flag)的功能是， 用深度优先搜索法在以 邻接表存储的无向网 G 中考察顶点 u、v 是否在同一个连通分量中，如果在同一个连通分量中 则 flag=1，否则 flag=0。 void Findedge(ALGraph &G,int u,int v,int& flag) { ArcNode* G.vertices[u].flag=1; for(p=G.vertices[u].p;p=p-&nextarc)-.200.-第 7 章 图结构{ w=p-& if(w==v){flag=1;} if(!G.vertices[w].flag) Findedge(G,w,v,flag);} } (3) 函数 void MiniTree_Kruskal(ALGraph &T,MGraph G)的功能是，用克鲁斯卡尔算法求 以邻接矩阵存储的无向网 G 的最小生成树 T，T 以邻接表存储。 void MiniTree_Kruskal(ALGraph &T,MGraph G) { int i,k,j,u,v, ArcNode* pr,*pr1; Edge *edge,/*以下语句的功能是对生成树 T 进行初始化*/T.vertices=new VexNode[G.vexnum]; T.arcnum=G.vexnum-1; T.kind=G. T.vexnum=G. for(i=0;i&T.i++) { T.vertices[i].data=G.vexs[i]. T.vertices[i].flag=0; T.vertices[i].nextarc=NULL; } EdgeSort(edge,G); i=k=0;/*以下语句为 Kruskal 算法的实现过程*///为 T 的头结点数组动态分配内存 //设置 T 中的边数为 n-1 条//T 在初始状态有 n 个连通分量（零条边） //flag=0 表示该顶点未被访问 //设定所有单链表初始为空 //将 G 的所有边按序存储到 edge 中 //k 表示 T 中现有边的个数while(k&T.vexnum-1) { arc=edge[i++]; //取一条权值最小的边到 arc 中 u=arc.v1; v=arc.v2; flag=0; Findedge(T,u,v,flag); //判断 u、v 是否在同一个连通分量中 if(!flag) //如果 arc 不在 T 的同一个连通分量中则将其加入到 T 中 { pr=new ArcN //动态分配单链表结点 pr pr-&adjvex=v; pr-&weight=arc. pr-&nextarc=T.vertices[u]. T.vertices[u].nextarc= pr1=new ArcN //动态分配单链表结点 pr1 pr1-&adjvex=u; pr1-&weight=arc. pr1-&nextarc=T.vertices[v]. T.vertices[v].nextarc=pr1;