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

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

《《第7章图结构》习题解答.docx》由会员分享，可在线阅读，更多相关《《第7章图结构》习题解答.docx（114页珍藏版）》请在冰点文库上搜索。

《第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到顶点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满足：

时，称其为稀疏图（sparsegraph）；当e满足：

时称其为稠密图（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）为无向图及其部分子图。

（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条边（或弧）的图，必定满足关系如下：

（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的路径，则称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是一棵有向树。

一个有向图的生成森林由若干棵有向树组成，森林中含有图中全部顶点，但是只有足以构成若干棵不相交的有向树的弧。

显然，一个有向图生成的有向树或生成森林都不是唯一的。

关于“顶点位置”的说明：

在图的基本操作定义中，其“顶点位置”和“邻接点位置”仅是一个相对的概念。

从图的定义可以看出，图中所有顶点的位置都是平等的，可以将任意一个顶点看成是第一个或最后一个顶点，也无法将其排列成一个线性序列或层次关系。

在实际操作中，为了方便起见，需要将所有顶点按照某个任意选定的顺序排列起来（排列与图中顶点之间的关系无关）。

所以，“顶点在图中的位置”是指该顶点在这个人为的随意排列中的位置（或序号）。

同理，可以对某个顶点的所有邻接点按照某个任意选定的顺序进行排列。

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．邻接矩阵的定义

设G=（V,VR）是一个图，含有n个顶点，那么G的邻接矩阵是表示G中顶点之间相邻关系的n阶方阵An×n，下面分别根据有权图和无权图给出矩阵A的定义。

如果G是无权图，则A的定义为：

如果G是有权图，则A的定义为：

【例7.1】分别给出图7.1、图7.3中各图的邻接矩阵。

在图7.1（a）、图7.1（b）中，图的顶点顺序按

排列时的邻接矩阵分别如图7.9（a）、图7.9（b）所示；在图7.3（a）、图7.3（b）中，图的顶点顺序分别按

和

排列时的邻接矩阵分别如图7.9（c）、图7.9（d）所示。

显然，图的邻接矩阵有以下特点：

（1）当图中顶点的排列顺序确定后，该图的邻接矩阵是唯一确定的；

（2）无向图的邻接矩阵是对称的，可以采用压缩存储的方法仅存入其下三角（或上三角）部分的元素即可；

（3）在无向图中，顶点vi的度是其邻接矩阵A的第i行元素的和，即：

；

（4）在有向图中，顶点vi的出度是其邻接矩阵A的第i行元素的和，而入度是A的第i列元素的和，所以vi的度可以表示为：

（n为图中顶点的个数）。

2．邻接矩阵的存储表示与实现

（1）邻接矩阵的类型定义

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

typedefintVType;//为便于操作，定义顶点类型VType为int型

structVNode{intflag;VTypevex;};//顶点与访问情况类型VNode{访问次数,顶点信息}

structMGraph{//定义图的邻接矩阵类型MGraph

VNode*vexs;//描述顶点的数组指针vexs

VType*arcs;//邻接矩阵的数组指针arcs

intvexnum,arcnum;//顶点数vexnum和边或弧数arcnum

GKindkind;//图的种类标志kind

};

（2）查找图中顶点位置的操作

函数的功能是，返回顶点u在图G中的位置，查找失败返回0值。

intLocateVex_MG（MGraphG,VTypeu）

{inti;

for（i=0;i

if（G.vexs[i].vex==u）break;

if（i

elsereturn（0）;

}

（3）邻接矩阵的建立操作

函数的功能是，根据图G的种类标志kind建立图G的所有信息。

#include"iostream.h"

voidCreateGraph_MG（MGraph&G,GKindkind）

{

inti,j,k;

VTypeu,v;

cout<<"输入顶点数vexnum和弧数arcnum:

";

cin>>G.vexnum>>G.arcnum;

G.kind=kind;

G.vexs=newVNode[G.vexnum];//为G.vexs分配存储空间

G.arcs=newVType[G.vexnum*G.vexnum];//为G.arcs分配存储空间

cout<<"按某种顺序输入"<

\n";

for（i=0;i

{G.vexs[i].flag=0;//flag=0表示该顶点未被访问

cin>>G.vexs[i].vex;//输入所有顶点的信息到G.vexs中

}

for（i=0;i

for（j=0;j

G.arcs[i*G.vexnum+j]=0;

if（G.kind==DG||G.kind==UDG）

cout<<"输入图中"<

\n";

else

cout<<"输入图中"<

\n";

for（k=0;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。

voidDisplyMG（MGraphG）

{inti,j;

for（i=0;i

{for（j=0;j

cout<

cout<

}

}

（5）演示程序主函数

程序中分别建立有向图G1、无向图G2、有向网G3和无向网G4的邻接矩阵，并显示输出每个邻接矩阵的数据信息。

voidmain（）

{MGraphG1,G2,G3,G4;

GKindgk1=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";

CreateGraph_MG（G3,gk3）;

cout<<"建立一个无向网的邻接矩阵G4:

\n";

CreateGraph_MG（G4,gk4）;

cout<<"有向网G3的邻接矩阵为:

\n";

DisplyMG（G3）;

cout<<"无向网G4的邻接矩阵为:

\n";

DisplyMG（G4）;

}程序运行演示结果为：

建立一个有向图的邻接矩阵G1:

输入顶点数vexnum和弧数arcnum:

68↙

按某种顺序输入6个顶点的值:

123456↙

输入图中8条边（弧）的信息uv:

1214313643546165↙

建立一个无向图的邻接矩阵G2:

输入顶点数vexnum和弧数arcnum:

67↙

按某种顺序输入6个顶点的值:

123456↙

输入图中7条边（弧）的信息uv:

12142326535654↙

有向图G1的邻接矩阵为:

010100

000000

100001

001000

000100

100010

无向图G2的邻接矩阵为:

010100

101001

010010

100010

001101

010010

***************************************

建立一个有向网的邻接矩阵G3:

输入顶点数vexnum和弧数arcnum:

44↙

按某种顺序输入4个顶点的值:

1234↙

输入图中4条边（弧）和权的信息uvw:

127131345419↙

建立一个无向网的邻接矩阵G4:

输入顶点数vexnum和弧数arcnum:

55↙

按某种顺序输入5个顶点的值:

12345↙

输入图中5条边（弧）和权的信息uvw:

1294184234513512↙

有向网G3的邻接矩阵为:

0710

0000

0005

9000

无向网G4的邻接矩阵为:

09080

90030

000012

83001

001210

说明：

（1）程序演示中建立的是图7.1、图7.3中4个图的邻接矩阵：

G1.arcs、G2.arcs、G3.arcs、G4.arcs。

从运行结果可以看出与图7.9的形式一致。

（2）在图的邻接矩阵存储结构上也容易实现其它基本操作，比如，对于无向图G中返回顶点v的第一个邻接点位置的基本操作函数：

intFirstAdjVex_MG（MGraphG,VTypev）。

算法的实现过程是：

1）根据顶点信息v，通过调用函数intLocateVex_MG（MGraphG,VTypev）找到v在G中的位置i；

2）在G的邻接矩阵中寻找第i行中第一个非零元素所在的列号j；

3）如果j存在函数返回j+1，否则返回0值。

类似地可以给出函数：

intNextAdjVex_MG（MGraphG,VTypev,VTypew）的算法实现代码。

（3）用邻接矩阵表示有n个顶点的图G时，查找边（或弧）的时间复杂度为O（n2）。

由于邻接矩阵的存储空间仅与顶点数n有关，而与边无关，因此，当图G的顶点较多而边数又很少时，其边的查找效率会很低。

为此，下面给出图的另一种存储结构，即图的邻接表表示法。

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．逆邻接表

在图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;//定义头结点数组指针vertices

intvexnum,arcnum;