搜索
第7章图结构-.167.-第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第7章图结构-.168.-到顶点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）完全图(Completedgraph)用n表示图中的顶点数，则具有n(n-1)/2条边的无向图称为无向完全图；具有n(n-1)条弧的有向图称为有向完全图。当图G中边(或弧)的总数e满足：logenn时，称其为稀疏图(sparsegraph)；当e满足：logenn时称其为稠密图(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)为无向图及其部分子图。第7章图结构-.169.-（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）出度(Outdegree)和入度(Indegree)在有向图中，顶点v的出度是指以v为弧尾的弧的数目，记为OD(v)；顶点v的入度是指以v为弧头的弧的数目，记为ID(v)；顶点v的度是指v的出度、入度的和，记为TD(v)。一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点e条边（或弧）的图，必定满足关系如下：11()2niieTDv（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第7章图结构-.170.-的路径，则称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是一棵有向树。一个有向图的生成森林由若干棵有向树组成，森林中含有图中全部顶点，但是只有足以构成若干棵不相交的有向树的弧。显然，一个有向图生成的有向树或生成森林都不是唯一的。关于“顶点位置”的说明：在图的基本操作定义中，其“顶点位置”和“邻接点位置”仅是一个相对的概念。从图的定义第7章图结构-.171.-可以看出，图中所有顶点的位置都是平等的，可以将任意一个顶点看成是第一个或最后一个顶点，也无法将其排列成一个线性序列或层次关系。在实际操作中，为了方便起见，需要将所有顶点按照某个任意选定的顺序排列起来（排列与图中顶点之间的关系无关）。所以，“顶点在图中的位置”是指该顶点在这个人为的随意排列中的位置（或序号）。同理，可以对某个顶点的所有邻接点按照某个任意选定的顺序进行排列。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．邻接矩阵的定义第7章图结构-.172.-设G=(V,VR)是一个图，含有n个顶点，那么G的邻接矩阵是表示G中顶点之间相邻关系的n阶方阵An×n，下面分别根据有权图和无权图给出矩阵A的定义。如果G是无权图，则A的定义为：1(,),[][]0ijRijRvvVvvVAij或其它情况如果G是有权图，则A的定义为：00(,),[][]ijijRijRijwvvVvvVAij或权值其它情况(为操作统一此处用而非)（w0）【例7.1】分别给出图7.1、图7.3中各图的邻接矩阵。在图7.1(a)、图7.1(b)中，图的顶点顺序按123456,,,,,vvvvvv排列时的邻接矩阵分别如图7.9(a)、图7.9(b)所示；在图7.3(a)、图7.3(b)中，图的顶点顺序分别按,,,ABCD和,,,,ABCDE排列时的邻接矩阵分别如图7.9(c)、图7.9(d)所示。显然，图的邻接矩阵有以下特点：(1)当图中顶点的排列顺序确定后，该图的邻接矩阵是唯一确定的；(2)无向图的邻接矩阵是对称的，可以采用压缩存储的方法仅存入其下三角（或上三角）部分的元素即可；(3)在无向图中，顶点vi的度是其邻接矩阵A的第i行元素的和，即：10()[][]nijTDvAij；(4)在有向图中，顶点vi的出度是其邻接矩阵A的第i行元素的和，而入度是A的第i列元素的和，所以vi的度可以表示为：1100()[][][][]nnijjTDvAijAji（n为图中顶点的个数）。2．邻接矩阵的存储表示与实现(1)邻接矩