《第7章 图结构》习题解答

本文格式为Word版，下载可任意编辑——《第7章图结构》习题解答第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是图中所有顶点之间的关系集，若∈VR，则表示从顶点v

-.167.-

第7章图结构

到顶点w的一条弧。

例如，在图7.1(a)所示的图G中的弧有：,,,,,和,共8条弧。（3）弧尾(Tail)弧的起始点。

（4）弧头(Head)弧的终端点。一条弧用有序对符号“〞来表示。

（5）有向图(Digraph)由顶点和弧组成的图称为有向图。譬如，图7.1(a)表示一个有向图。（6）边(Edge)设VR是图中所有顶点之间的关系集，若∈VR必有∈VR，则以无序对符号(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）完全图(Completedgraph)用n表示图中的顶点数，则具有n(n-1)/2条边的无向图称为无向完全图；具有n(n-1)条弧的有向图称为有向完全图。当图G中边(或弧)的总数e满足：

e?nlogn时，称其为稀疏图(sparsegraph)；当e满足：e?nlogn时称其为稠密图(dense

graph)。显然，完全图是稠密图，反之不然。图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)，若弧∈VR，则称顶点v邻接到顶点w，顶点w邻接自顶点v。

（13）度(Degree)在无向图中，顶点v的度是指和v相关联的边的数目，记为TD(v)。（14）出度(Outdegree)和入度(Indegree)在有向图中，顶点v的出度是指以v为弧尾的弧的数目，记为OD(v)；顶点v的入度是指以v为弧头的弧的数目，记为ID(v)；顶点v的度是指v的出度、入度的和，记为TD(v)。

一般地，假使顶点vi的度记为TD(vi)，那么一个有n个顶点e条边（或弧）的图，必定满足关系如下：

1ne??TD(vi)

2i?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）连通图(Connectedgraph)在无向图G=(V,VR)中，假使从顶点v到顶点w有路径，则称v与w是连通的。假使对于任意两个顶点v,w∈V都是连通的则称G是连通图。

（18）连通分量(Connectedcomponent)无向图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满足或∈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)或弧；（10）删除弧DeleteArc(&G,v,w)函数功能是，在图G中删除边(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的定义为：

?1A[i][j]???0假使G是有权图，则A的定义为：

(vi,vj)?VR或?vi,vj??VR其它状况

A[i][j]???wij?0(vi,vj)?VR或?vi,vj??V（权值wij?0）R

其它状况(为操作统一此处用0而非?)分别给出图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?0n?1(4)在有向图中，顶点vi的出度是其邻接矩阵A的第i行元素的和，而入度是A的第i列元素的和，所以vi的度可以表示为：TD(vi)??A[i][j]??A[j][i]（n为图中顶点的个数）。

j?0j?0n?1n?12．邻接矩阵的存储表示与实现(1)邻接矩阵的类型定义

typedefenum{DG,DN,UDG,UDN}GKind;//图的类型GKind{有向图,有向网,无向图,无向网}

-.172.-

第7章图结构

typedefintVType;//为便于操作，定义顶点类型VType为int型structVNode{intflag;VTypevex;};//顶点与访问状况类型VNode{访问次数,顶点信息}structMGraph{//定义图的邻接矩阵类型MGraphVNode*vexs;//描述顶点的数组指针vexsVType*arcs;//邻接矩阵的数组指针arcsintvexnum,arcnum;//顶点数vexnum和边或弧数arcnumGKindkind;//图的种类标志kind};

(2)查找图中顶点位置的操作

函数的功能是，返回顶点u在图G中的位置，查找失败返回0值。intLocateVex_MG(MGraphG,VTypeu){inti;for(i=0;i>G.vexnum>>G.arcnum;G.kind=kind;G.vexs=newVNode[G.vexnum];//为G.vexs分派存储空间G.arcs=newVType[G.vexnum*G.vexnum];//为G.arcs分派存储空间cout>G.vexs[i].vex;//输入所有顶点的信息到G.vexs中}for(i=0;i>u>>v;}//根据顶点信息找到所在位置while(!((i=LocateVex_MG(G,u))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];//输入相应边或弧的权重wif(G.kind==UDG||G.kind==UDN)//无向图的邻接矩阵是对称的G.arcs[j*G.vexnum+i]=G.arcs[i*G.vexnum+j];}

(4)显示输出邻接矩阵的操作

函数功能是，显示输出图G的邻接矩阵G.arcs。voidDisplyMG(MGraphG){inti,j;for(i=0;i第7章图结构

在图G的邻接表中，顶点v的相邻元素可以通过遍历该顶点对应的单链表求得，设该链表中结点的个数为k那么，G为无向图时k表示v的度，G为有向图时k表示v的出度。假使求顶点v的入度，则需要遍历邻接表中的所有单链表，统计与v的序号一致的结点个数。这样处理很不便利，为此，仿照邻接表，建立一个逆邻接表，即对每个顶点v建立一个单链表，把所有邻接于v的顶点链接在一起，此时该单链表的长度即为v的入度。

例如，图7.11(a)所示的有向图可用逆邻接表表示为图7.12。

3．邻接表的存储表示与实现(1)邻接表存储结构的类型定义

定义单链表结点类型ArcNode：

structArcNode{intadjvex,weight;ArcNode*nextarc;};定义链表头结点结构类型VexNode：

structVexNode{VTypedata;intflag;ArcNode*nextarc;};定义邻接表存储结构的类型ALGraph：structALGraph{VexNode*vertices;//定义头结点数组指针verticesintvexnum,arcnum;//顶点数vexnum和边或弧数arcnumGKindkind;//图的种类标志kind};

(2)查找图中顶点位置的操作

函数的功能是，返回顶点u在图G中的位置，查找失败返回0值。intLocateVex_AL(ALGraphG,VTypeu){inti;for(i=0;i>G.vexnum>>G.arcnum;

G.vertices=newVexNode[G.vexnum];//为顶点数组分派内存空间cout>G.vertices[i].data;//输入所有顶点的信息到vex中G.vertices[i].nextarc=NULL;//设定初始的单链表为空}

if(G.kind==DG||G.kind==UDG)cout>u>>v;}while(!((i=LocateVex_AL(G,u))i--,j--;//i,j从位置值转换为下标值pr=newArcNode;//动态分派单链表结点prpr->adjvex=j;pr->weight=0;if(G.kind==DN||G.kind==UDN)cin>>pr->weight;//输入对应边（弧）的权值pr->nextarc=G.vertices[i].nextarc;//将结点pr插入到第i个链表的首部G.vertices[i].nextarc=pr;if(G.kind==UDG||G.kind==UDN)//对于无向图(或网)将结点pr1插入到第j个链表的首部{pr1=newArcNode;//动态分派单链表结点pr1pr1->adjvex=i;pr1->weight=pr->weight;pr1->nextarc=G.vertices[j].nextarc;G.vertices[j].nextarc=pr1;//将结点pr1插入到第j个链表的首部}//endswitch}//endfor

(4)显示输出邻接矩阵的操作

函数功能是，显示输出图G的邻接链表中的所有信息。voidDisplyAL(ALGraphG)//显示邻接矩阵G{inti;

-.178.-

第7章图结构

}

ArcNode*p;

for(i=0;inextarc;}cout

第7章图结构7.6拓扑排序

拓扑排序是有向图的重要应用之一，它在实际中的应用很广。有向无环图是描述工程和系统进程的有效工具。例如，要完成一项大工程(project)可以把它分为若干个称为活动(activity)的子工程，当这些活动都完成时，整个工程即告终止。而这些活动的安排有时要有特别的要求，譬如有些活动必需安排在另外一些活动已完成以后才能开始，而有些活动并不依靠于任何活动的完成等。类似这样的问题，可以用有向无环图来解决。

7.6.1AOV网

在有向图中，以顶点表示活动，有向边表示活动之间的优先关系，我们把这样的有向图称为顶点表示活动的网络(ActivityOnVertexNetwork)，简称为AOV网。在AOV网中，若从顶点vi到顶点vj有一条有向路径，则称vi是vj的前驱，vj是vi的后继；若是AOV网中的一条弧，则称vi是vj的直接前驱，vj是vi的直接后继。假使vi是vj的前驱或直接前驱，则vi活动必需在vj活动开始前终止；而vj活动必需在vi活动终止后才能开始。

在AOV网中不允许出现回路，由于假使有回路存在则表示必有某个活动是以自己为先决条件的，即存在活动vi，vi既是其本身的前驱又是其本身的后继，这显然是矛盾的。

例如，图7.30(a)列出了某大学计算机专业学生所学的一些课程，图7.30(b)用有向图表示课程之间的先后关系。

课程号C1C2C3C4C5C6课程名称C语言程序设计离散数学数据结构汇编语言语言设计与分析计算机组成原理先导课无C1C1,C2C1C3,C4C11课程号C7C8C9C10C11C12课程名称编译原理操作系统高等数学线性代数普通物理数值分析先导课C3,C5C3,C6无C9C9C1,C9,C10(a)某大学计算机专业学生所学的一些课程

由图可以看出，先学习课程C1、C2以后才可以开始学习课程C3，即C1、C2为C3的直接前导课程；只有学习C3、C4以后才可以开始学习课程C5；只有学习C3、C5以后才可以学习

-.212.-

第7章图结构

课程C7。所以C7的直接前导课程为C3、C5，而C7的所有前导课程为C1、C2、C3、C4、C5。

检测AOV网中是否存在环路的方法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点均在该序列中，则该AOV网中必定不存在环路，否则必有环路存在。

7.6.2拓扑排序

如何安排AOV网中各个活动的先后次序就是拓扑排序问题。所谓拓扑排序，即是把AOV网中各个顶点依照它们之间的优先关系排列成一个线性序列，这个序列称为拓扑有序序列。在AOV网中，假使从顶点vi到顶点vj有有向路径存在，则在拓扑有序序列中，vi必定排在vj的前面。假使在AOV网中存在环路，则不存在该网的拓扑有序序列；否则，任何有向无环网其所有顶点都可以排列在一个拓扑有序序列中。

显然，一个AOV网的拓扑有序序列不是唯一的。对图7.30(b)所示的有向图进行拓扑排序，可以得到多种不同的拓扑有序序列，下面给出其中的三种拓扑有序序列：

?C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C8,C7??C1,C9,C4,C10,C11,C2,C12,C3,C6,C5,C7,C8??C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8?对AOV网进行拓扑排序的步骤是：

首先任意选取一个入度为零的顶点输出，再从图中删除该顶点和所有以它为尾的弧。重复以上步骤，直至有向图中全部顶点都被输出，或者还没有输出全部顶点，但已找不到入度为零的顶点为止。第一种状况说明该有向图中不存在有向环路，拓扑排序已完成；对于其次种状况则说明该有向图中存在有向环路。

1．拓扑排序的算法思想

为了实现拓扑排序的方法，可以采用邻接表作为有向图的存储结构，并且在头结点中增加一个存放顶点入度的域(indegree)。每个顶点入度域的值随邻接表动态生成过程中累计得到。也可以另设一个数组(indegree)用于存放所有顶点的入度。在入度数组(indegree)中，入度为0的顶点即为可以删除的没有前驱的顶点。删除顶点以及以该顶点为尾的所有弧的操作，可以通过对弧头顶点入度域的值减1来实现。为了避免重复检测入度为0的顶点，可以另设一个栈(Stack)来存储所有入度为0的顶点下标。下面列出拓扑排序算法的具体步骤：

(1)假使入度数组(indegree)是另设的，则初始化该数组；

(2)将邻接表中所有入度为0的顶点下标进栈S，初始化输出顶点计数器count；(3)在栈S不为空时：

a)出栈并输出顶点i，count++；

b)将顶点i的所有直接后继顶点k的入度减1。假使减1后，顶点k的入度为0，则顶点k进栈S。

(4)假使S为空时countadjvex]++;p=p->nextarc;}}

S.s=newint[num];S.t=0;

for(i=0;iadjvex]--;if(!indegree[p->adjvex])S.s[S.t++]=p->adjvex;p=p->nextarc;}}cout第7章图结构

函数voidDisplyAMLG(AMLGraphG)按邻接表的方式显示当前邻接多重链表表示的无向图G的相关信息。

voidDisplyAMLG(AMLGraphG){inti;EBox*p;coutivex==i)coutivex==i)p=p->ilink;//指针指向下一个边结点elsep=p->jlink;}coutnextarc)//进入下一层{w=p->adjvex;

-.189.-

第7章图结构

}

}

if(!G.vertices[w].flag)DFS_ALG(G,w);//通过递归调用实现深度优先遍历

(2)对图的深度优先遍历

函数voidDFSTraverse_ALG(ALGraphG)的功能是，通过重复调用函数DFS_ALG(G,v)实现对邻接表G的深度优先遍历。

voidDFSTraverse_ALG(ALGraphG){intv;for(v=0;v

第7章图结构

上的权值。

lowcost域的具体含义为：

vi?U??1?closedge[i?1].lowcost??0vi与U不关联

??0v到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

structCloseDge{VTypeadjvex;intlowcost;};

(1)函数voidMiniTree_Prim(MGraphG,VTypeu)的功能是，对于邻接矩阵存储的网G，从顶点u开始，用普里姆算法构造一棵最小代价生成树，并输出该树的结点和边的权值。

voidMiniTree_Prim(MGraphG,VTypeu){inti,j,k,min,max;CloseDge*closedge=newCloseDge[G.vexnum];if(!(k=LocateVex_MG(G,u)))return;k--;//将k转换为顶点u的下标

-.197.-

第7章图结构

for(max=G.arcs[0],i=0;i0k=j;}cout=0;m--){if(edge[m].adjvex>w)edge[m+1]=edge[m];elsebreak;}edge[m+1]=arc;k++;}}

(2)函数voidFindedge(ALGraphArcNode*p;G.vertices[u].flag=1;for(p=G.vertices[u].nextarc;p;p=p->nextarc)

-.200.-

第7章图结构

{w=p->adjvex;if(w==v){flag=1;return;}if(!G.vertices[w].flag)Findedge(G,w,v,flag);}}

(3)函数voidMiniTree_Kruskal(ALGraphArcNode*pr,*pr1;Edge*edge,arc;

/*以下语句的功能是对生成树T进行初始化*/