搜索
第六章图在数据结构中，图比前面章节所讲述的的线性表、树等都更为复杂。而且，图这种数据结构在解决实际问题中也有着广泛的应用，比如说：当驱车旅游时，需要在众多路线中选择一条最佳路线；对大型工程进行管理时，怎样才能够提前完成工程；在电路板上布线时，如何保证在连线最短的情况下，连接多个节点。这些问题都可以通过本章所讲述的内容解决。6·1图的概念6.1.1图的定义图就是顶点和边的集合。一般描述为图G={V,E}，V(G)为图G的顶点集合，必须是有穷非空集合，E(G)为图G的边集合，可以是空集。图6.1.1列出了两个典型的图。6.1.2图的术语顶点：图中的数据元素。边：连接图中顶点的连线，表示两个顶点之间的某种关系。可以用顶点对来表示，如图6.1.1(a)中顶点V1和V2之间的关系可以用(V1,V2)表示，图6.1.1(b)中顶点V1到顶点V2之间的关系可以用V1,V2来表示。弧：连接图中顶点的有向连线，表示两个顶点之间的某种关系。可以用顶点对来表示，图6.1(b)中顶点V1到顶点V2之间的关系可以用顶点对V1,V2来表示。弧头：弧的终止顶点。弧尾：弧的开始顶点。无向图：由顶点和边组成，边不具备方向性。有向图：由顶点和弧组成。图6.1.1图6.1.2完全图：图中的任意两个顶点之间都存在一条边。如图6.1.2(a)所示。有向完全图：图中的任意两个顶点之间都存在一对相反方向的弧。如图6.1.2(b)所示。稀疏图：具有很少边或弧的图。稠密图：具有很多边或弧的图。权：与图中的边或者弧相关的数。网：带权图。子图：如果存在这样的两个图：G={V,E}G’={V’,E’}那么称图G’是图G的子图。如图6.1.3所示，图6.1.3(b)和图6.1.3(c)是图6.1.3(a)的子图。路径：从起始顶点到终止顶点所经过的顶点的序列。路径长度：路径上边或者弧的数量。简单路径：没有重复顶点的路径。连通图：任意两个顶点之间都至少存在一条路径的无向图。连通分量：无向图的极大连通子图称为它的连通分量。强连通图：任意两个顶点之间都至少存在一条路径的有向图。强连通分量：有向图的极大连通子图称为它的强连通分量邻接：如果(Vi,Vj)是E(G)中的一条无向边,那么顶点Vi和顶点Vj是邻接的；如果Vi,Vj是E(G)中的一条有向边,那么顶点Vi邻接到（至）Vj,顶点Vj邻接自Vi的。关联：如果(Vi,Vj)是E(G)中的一条无向边,那么边(Vi,Vj)是和顶点Vi、Vj相关联的；如果Vi,Vj是E(G)中的一条有向边,那么边Vi,Vj是和顶点Vi、Vj相关联的。度：无向图中，和某顶点相关联的边的数量，称为这个顶点的度。入度：有向图中，以某个顶点为弧头的弧的数量，称为这个顶点的入度。出度：有向图中，以某个顶点为弧尾的弧的数量，称为这个顶点的出度。回路：如果一条路径的第一个顶点和最后一个顶点是同一个顶点，那么这条路径构成了一个回路。简单回路：除了第一个和最后一个顶点外，不再有重复顶点的回路，称为简单回路。自回路：如果一条边的头和尾都是同一个顶点，称之为自回路。自回路的方向是没有意义的，它既可以是有向边，也可以是无向边。平行：如果有若干条边的头和尾都是相同的，称之为平行边。多重图：包含有平行边的图都称之为多重图。简单图：既不包含自回路也不包含平行边的图，称为简单图。本章以后所讲的都是简单图。图6.1.36.1.3图的抽象数据类型上面已经详细讨论了图的定义及相关概念，下面我们将重点围绕图的抽象数据类型进行讨论。ADT6图的抽象数据类型ADTGraph｛Dset：非空有限顶点集合V。Rset：非空有限顶点由多条边连接起来，构造成的顶点和边的关系。OPSet：CreateGraph(&G);建立图的算法DestroyGraph(&G);删除图的算法LocateVex(&G,v);在图中查找顶点vGetVex(&G,v);获取顶点v的值PutVex(&G,v,value);修改顶点v的值DFSTraverse(&G,v);从顶点v开始，对图进行深度优先搜索BFSTraverse(&G,v);从顶点v开始，对图进行宽度优先搜索｝6.2图的存储结构相对于树来说，图的结构更为复杂，顶点、边之间的联系更为密切，简单的二重链表，甚至更多重链表已经无法表达它们之间的这些复杂关系了。由于图中各个顶点的度差别可能很大，这就给图的存储表示带来了很大的困难。这里先给出几种常见的存储表示方法，但要强调的是，在解决实际问题的时候，并不一定要拘泥于这里所给的描述，可以根据实际情况来最终确定存储表示的方法。6．2．1邻接矩阵表示法1．邻接矩阵的概念邻接矩阵表示法是一种简单的存储表示方法，它的优点是简单，缺点就是空间开销在某些情况下可能比较大，而且空间的利用率可能较低。这种表示法既适用于无向图，也适用于有向图。这种方法的基本思想就是，对于有n个顶点的图，就定义一个n阶矩阵，把各个顶点之间存在的、不存在的边都穷举出来。对于不存在的边，带权图和不带权图的实现上有所差别。如果图G是无向不带权图，可以用下面的邻接矩阵来表示：如果图G是有向不带权图，可以用下面的邻接矩阵来表示：如果图G是无向带权图，可以用下面的邻接矩阵来表示：如果图G是有向带权图，可以用下面的邻接矩阵来表示：图6.2.1列举出了四种典型的图，图6.2.2列举出了对应的邻接矩阵。从图示中可以看出，无向图对应的邻接矩阵是对称的，有向图对于的邻接矩阵则不一定对称。采用这种表示方法，可以根据矩阵的第i行j列元素的值，直接判断某两个顶点之间是否邻接。而且计算顶点的度也很方便：对于无向图中的顶点Vi，它的度就是邻接矩阵中第i行的和，对于有向图来中的顶点Vi，它的入度就是第i列的和,出度就是第i行的和。图6.2.1图6.2.22．邻接矩阵的实现按照前面的描述，图可以采用一个二维数组来存储表示。具体的存储结构定义如下：typedefstruct{int**data;intvertex_num;intedge_num;}Graph；data指向存储数据的存储空间，vertex_num指示顶点的数量，edge_num指示边的数量。3．基于邻接矩阵表示的图的建立采用邻接矩阵表示方法，可以用下面的算法建立图。基于邻接矩阵表示的图的建立算法//基于邻接矩阵表示的有向带权图的建立算法voidCreateGraph(Graph&g){intn,first,second;cout请输入边的数量;cing.edge_num;cout请输入顶点的数量;cing.vertex_num;g.data=newint*[g.vertex_num];for(n=0;ng.vertex_num;n++)g.data[n]=newint[g.vertex_num];for(first=0;firstg.vertex_num;first++)for(second=0;secondg.vertex_num;second++)g.data[first][second]=INFINITY;for(n=0;ng.edge_num;n++){cout请输入第n+1条弧的弧头顶点的序号;cinfirst;cout请输入第n+1条弧的弧尾顶点的序号;cinsecond;cout请输入权;cing.data[first][second];}}该算法虽然只是介绍了有向带权图的建立，稍加改造，同样可以建立基于邻接矩阵的其它类型的图。6．2．2邻接表表示法1.邻接表的概念对于图G中的某个顶点Vi，把与它相邻接的所有顶点（如果是有向图,则是所有邻接自该顶点的所有顶点）串起来，构成一个单链表，这个链表就称为顶点Vi的邻接表。如果图G有n个顶点，那么就会得到n条邻接表。为了有效地对这n条邻接表进行有效的管理，每条邻接表的前面都增设一个表头结点。所有的表头结点可以存储在一个数组中。为了避免各顶点信息的重复存储，可以规定，各顶点的基本信息存放在表头结点中，表头结点的基本格式如图6.2.3所示。data分量存储各表头的基本信息。而在邻接表中，只需要把边表示出来就可以了。这些边的一个顶点是相同的，需要把边的另外一个顶点表示出来；另外，边本身可能存在权等信息，也需要表示出来。其基本格式如图6.2.4所示。another_vertex表示该边的另外一个顶点在表头结点数组中的下标，info表示该边的权等信息，next指向链表中的下一个结点。如图6.2.5所示，给出了一个无向图的邻接表表示。如图6.2.6所示，给出了一个有向图的邻接表表示。一个图对应的邻接矩阵是唯一的，而对应的邻接表却不是唯一的，因为邻接表中各结点出现的顺序和建立图时的输入顺序有关。图6.2.3图6.2.4图6.2.5图6.2.6当解决实际问题时，到底是采用邻接矩阵表示好，还是采用邻接表表示好呢？下面作一个分析。邻接表表示中的一条单链表，对应于邻接矩阵的一行，边表中结点个数等于一行中非零元素的个数。若无向图G具有n个顶点e条边的图G，那么它的邻接表表示中有n个表头结点和2e个链表结点；若有向图G具有n个顶点e条边的图G，那么它的邻接表表示中有n个表头结点和2e个链表结点；不管图G是否有向，只要有n个顶点，那么在邻接矩阵表示法中，就要占据n*n个存储单元。如果图G是稀疏图，邻接表表示比邻接矩阵表示节省存储空间；如果不是是稀疏图，因为邻接表中有额外的附加链域，那么采取邻接矩阵表示法较好。2.逆邻接表的概念在邻接表表示中，对于无向图，顶点的度很容易计算，第i个单链表中的结点个数就是顶点Vi的度。对于有向图，第i个单链表中的结点个数就是顶点Vi的出度，要想计算顶点的入度，就需要访问每一条单链表。在某些情况下，可能要大量计算有向图顶点的出度，在某些情况下，可能要大量计算有向图顶点的入度。为了方便地解决后一个问题，这里引进逆邻接表的概念。逆邻接表的概念和邻接表的概念基本一样，唯一的差别在于：邻接表表示中，如果是有向图,是把所有邻接自某顶点的所有顶点串起来，构成一条单链表；而在逆邻接表表示中，是把所有邻接至某顶点的所有顶点串起来，构成一条单链表。图6.2.7给出了一个有向图的逆邻接表表示。3.邻接表的实现邻接表中，结点的定义如下：typedefstruct{intanother_vertex;InfoTypeinfo;AdjNode*next;}AdjNode；another_vertex表示该边的另外一个顶点在表头结点数组中的下标，info表示该边的权等信息，next指向链表中的下一个结点。表头结点数组的定义如下：typedefstruct{ETypedata;AdjNode*head;}AdjList；图6.2.7typedefstruct{AdjList*head_list;intvertex_num;//顶点数intedge_num;//边数}AdjGraph；4.基于邻接表的图的建立采用邻接表表示方法，可以用下面的算法建立图。基于邻接表表示的图的建立算法//基于邻接表表示的有向带权图的建立算法voidCreateGraph(AdjGraph&g){intn,first,second,weight;AdjNode*p;cout请输入边的数量;cing.edge_num;cout请输入顶点的数量;cing.vertex_num;g.head_list=newAdjList[g.vertex_num];for(n=0;ng.vertex_num;n++)g.head_list[n].head=NULL;for(n=0;ng.edge_num;n++){cout请输入第n+1条弧的弧头顶点的序号;cinfirst;cout请输入第n+1条弧的弧尾顶点的序号;cinsecond;cout请输入该弧的权;cinweight;p=newAdjNode;p-info=weight;p-another_vertex=second;p-next=g.