数据结构——图

5.1图的基本概念图是一种重要的，比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系。但在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。图的应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它分支中。图的定义及相关术语(1)图的定义：图G由两个集合V(G)和E(G)所组成，记作G=(V, E)。其中，V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。(2)有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号括起一对顶点表示。(6)完全图。假设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图；含有e=n(n-1)条弧的有向图称作有向完全图。(7)稠密图与稀疏图。若图的边或弧的数目接近于相应完全图的边或弧的数目，则称之为稠密图，否则称为稀疏图。(9)简单路径：序列中顶点不重复出现的路径。(10)简单回路：序列中第一个顶点和最后一个顶点相同的简单路径。(11)连通图：在无向图中，若每一对顶点之间都有路径，则称此图为连通图。(12)连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。连通图BACDFEBACDFE非连通图(13)强连通图：在有向图中，若每一对顶点u和v之间都存在v到u及u到v的路径，则称此图为强连通图。(14)强连通分量：各个强连通子图称作该有向图的强连通分量。强连通图ABECFABECF非强连通图ACDFETD(B)=3，TD(A)=2BABECFID(B)=2，OD(B)=1TD(B)=ID(B)+OD(B)=3建立和销毁图结构插入或删除顶点对邻接点的操作访问顶点遍历图插入和删除弧基本操作5.2图的存储结构图的存储结构一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示*三、有向图的十字链表存储表示*四、无向图的邻接多重表存储表示根据图的定义可知，一个图的逻辑结构分两部分，一部分是组成图的顶点的集合；另一部分是顶点之间的联系，即边或弧的集合。可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵。设G=(V，E)是有n(n≥1)个顶点的图，则G的邻接矩阵A是一个n×n阶矩阵。Aij={0若(Vi,Vj)或Vi,VjE(G)1若(Vi,Vj)或Vi,VjE(G)一、图的数组(邻接矩阵)存储表示定义:矩阵的元素为BADFEC010010100011000101001001110000011100ABCDEFABCDEF有向图的邻接矩阵ABDCE0101000100000010010011000ABCDE特点无向图的邻接矩阵是对称的;有向图的邻接矩阵不一定对称。对于无向图，邻接矩阵第i行(或第i列)的元素之和是顶点Vi的度。对于有向图，邻接矩阵第i行元素之和为顶点Vi的出度；第i列的元素之和为顶点Vi的入度。使用邻接矩阵法容易判断任意两个点的邻接关系。网的邻接矩阵可定义为ijijijW(V,V)V,VE(G)A[i,j]反之若或其中Wij是边(Vi,Vj)或弧Vi,Vj上的权值。邻接表是一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是链表；另一部分是向量。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点由三个域组成：adjvex、data和nextarc，如下图所示。二、图的邻接表存储表示邻接表中表结点的结点结构顶点Vi的邻接点在图中的位置指向顶点Vi的下一邻接点的指针adjvexdatanextarc权值为便于邻接表操作，在每个单链表上附设一个头结点，在头结点中有两个域：vexdata和firstarc。如下图所示。邻接表中头结点的结点结构vexdatafirstarc指向顶点Vi的第一个邻接点的指针存储Vi的名字或有关信息为了利用顺序存储结构的随机访问特性，邻接表中将每个单链表的头结点以顺序结构的形式存储，以便能随机访问任一顶点的单链表。邻接表的存储结构可以用C语言描述如下：#defineVTXUNMn/*n为图中顶点个数的最大可能值*/structarcnode{intadjvex;floatdata;structarcnode*nextarc;};typedefstructarcnodeARCNODE;structheadnode{intvexdata;ARCNODE*firstarc;}adjlist[VTXUNM];BACDFE0A141B0452C353D254E015F123•示例：无向图的邻接表有向图的邻接表ABDCE在有向图的邻接表中不易找到指向该顶点的弧，即难以确定某个顶点的入度。13242001234ABCDE1ABECD有向图的逆邻接表在有向图的逆邻接表中，每个顶点链接的是指向该顶点的弧。ABCDE303120012344有向带权图的邻接表231231437ABCABC734(a)(b)在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点(Vi和Vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，因此不及邻接矩阵方便。对一个图来说，邻接表不是惟一的，它取决于建立邻接表时，结点在每个单链表中的插入策略。另外，对于有向图，其邻接表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。5.3图的遍历图的遍历从图中某个顶点出发访问图中每个顶点一次且仅一次的过程。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。深度优先搜索广度优先搜索从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图中的其余顶点，直至图中所有和V0有路径相通的顶点都被访问到为止。一、深度优先搜索遍历图连通图的深度优先搜索遍历(用栈)W1、W2和W3均为V0的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。访问顶点V0：for(W1、W2、W3)若该邻接点Wi未被访问过，则从它出发进行深度优先搜索遍历。V0w1SG1SG2SG3w2w3w2算法分析1.深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法：设立一个一维数组，用来记录每个顶点是否被访问过，即“访问标志visited[w]”。2.如何判别V0的邻接点是否被访问？显然，这个遍历过程是个递归过程。在设计具体算法时，首先要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。例连通图G的邻接表表示如下图所示，以顶点V1为始点，按深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。42123123124(a)(b)31451672843528563867387847856V[i]5678连通图G及其邻接表解：先访问V1，再访问与V1邻接的V2，再访问V2的第一个邻接点，因V1已被访问过，则访问V2的下一个邻接点V4，然后依次访问V8，V5。这时，与V5相邻接的顶点均已被访问，于是反向回到V8去访问与V8相邻接且尚未被访问的V6，接着访问V3，V7，至此，全部顶点均被访问。相应的访问序列为：V1→V2→V4→V8→V5→V6→V3→V7。下面给出dfs的递归算法。#defineVTXUNMn/*n为图中顶点个数的最大可能值*/structarcnode{intadjvex;floatdata;structarcnode*nextarc;};typedefstructarcnodeARCNODE;structheadnode{intvexdata;ARCNODE*firstarc;};structheadnodeG[VTXUNM+1];intvisited[VTXUNM+1];voiddfs(structheadnodeG[],intv){ARCNODE*p;printf(''%d-'',G[v].vexdata);visited[v]=1;p=G[v].firstarc;while(p!=NULL){/*当邻接点存在时*/if(visited[p-adjvex]==0)dfs(G,p-adjvex);p=p-nextarc;/*找下一邻接点*/}}voidtraver(structheadnodeG[]){intv;for(v=1;v=VTXUNM;v++)visited[v]=0;for(v=1;v=VTXUNM;v++)ifvisited[v]==0dfs(G,v);}首先将图中每个顶点的访问标志设为FALSE,随后搜索图中每个顶点，如果未被访问过，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一个顶点。非连通图的深度优先搜索遍历需多次调用dfs算法。每调用一次dfs得到的顶点集合恰为图中一个连通分量的顶点集合，这些顶点集合中的顶点加上所有依附于这些顶点的边，便构成了非连通图的一个连通分量。非连通图的深度优先搜索遍历FFFFFFFFFTTTTTTTTTachdkfebg访问标志:访问次序:例如:012345678abchdekfgachkfedbg016234578二、广度优先搜索遍历图对连通图，从起始点v到其余各顶点必定存在路径。其中，vw1,vw2,vw8的路径长度为1；vw7,vw3,vw5的路径长度为2；vw6,vw4的路径长度为3。Vw1w8w3w7w6w2w5w4w1vw2w7w6w3w8w5w4从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止。连通图的广度优先搜索遍历例对图示连通图G，从顶点V1出发，写出顶点的广度优先遍历序列。解：按广度优先搜索法从V1开始遍历，访问V1，然后访问V1的邻接点V2，V3，再依次访问V2和V3的未曾被访问的邻接点V4，V5及V6，V7，最后访问V4的邻接点V8。遍历序列如下：V1→V2→V3→V4→V5→V6→V7→V842123123124(a)(b)31451672843528563867387847856V[i]5678连通图G及其邻接表注意，在bfs算法中，若W1在W2之前访问，则W1的邻接点也将在W2的邻接点之前访问，这里蕴涵了一个排队关系。在实现算法时，需设一个队列，每访问一个顶点后将其入队，然后将队头顶点出列，去访问与它邻接的所有顶点，重复上述过程，直至队空为止。下面给出bfs的相应算法。广度优先遍历算法。#defineVTXUNMnvoidbfs(structheadnodeG[],intv){intqueue[VTXUNM];intrear=VTXUNM−1,front=VTXUNM−1;inti;ARCNODE*p;printf(''%d-'',G[v].vexdata);visited[v]=1;rear=(rear+1)%VTXUNM;queue[rear]=v;/*访问过的顶点进队列*/while(rear!=front){front=(front+1)%VTXUNM;v=queue[front];p=G[v].firstarc;while(p!=NULL){if(visited[p-adjvex]==0){printf(''%d-'',G[p-adjvex].vexdata);visited[p-adjvex]=1;rear=(rear+1)%VTXUNM;queue[rear]=p-adjvex;}p=p-