数据结构-清华大学-殷人昆-05

第5章图清华大学计算机系殷人昆数据结构课件第五章图千门万户，纵横捭阖神奇的图应用建模的利器138-2图的基本概念图的存储表示图的遍历与连通性最小生成树最短路径活动网络第5章图138-3图的基本概念图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中，V={x|x某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,yV}或E={x,y|x,yV&&Path(x,y)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条单向通路,它是有方向的。138-4有向图与无向图在有向图中，顶点对x,y是有序的。在无向图中，顶点对(x,y)是无序的。完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为完全无向图。有n个顶点的有向图有n(n-1)条边,则此图为完全有向图。完全无向图无向图（自由树）有向图完全有向图00001111222265433138-5邻接顶点如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。0123子图0130123023138-6顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。路径在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。138-7路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。012301230123138-8连通图与连通分量在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。生成树一个连通图的生成树是其极小连通子图，在n个顶点的情形下，有n-1条边。138-9图的存储表示在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，定义：邻接矩阵(AdjacencyMatrix)否则或若,,0),(,1]][A.Edge[EjiEjiji138-10无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。0101101001011010A.edge0123012000101010A.edge138-11在有向图中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。若图中有n个顶点，e条边，邻接矩阵有n2个矩阵元素，对于无向图，其中有2e个非零元素，对于有向图，只有e个非零元素。如果e远远小于n2，则称该图为稀疏图，其邻接矩阵将是稀疏矩阵；否则该图为稠密图，邻接矩阵适用于稠密图。对于一个图来说，邻接矩阵表示是惟一的。138-12网络的邻接矩阵jiji,ji,jiji,ji,jijiji若或且若或且若,)(,)(),,(]][[0EEEEWA.edge863129542031068053290410A.edge138-13用邻接矩阵表示的图结构的定义#definemaxValueINT_Max//在limits.h中#definemaxEdges30//最大边条数#definemaxVertices10//最大顶点个数typedefcharVType;//顶点数据类型typedefintWType;//边上权值类型typedefstruct{//静态存储定义VTypeverticesList[maxVertices];//顶点表WTypeEdge[maxVertices][maxVertices];//邻接矩阵,可视为边之间的关系intnumVertices,numEdges;//当前顶点个数与边数}MGraph;138-14WTypeGetWeight(MGraph&G,intu,intv){//给出以顶点u和v为两端点的边上的权值if(u!=-1&&v!=-1)returnG.Edge[u][v];elsereturn0;}VTypeGetValue(MGraph&G,inti){//给出第i个顶点的数据值returni=0&&iG.numVertices?G.VerticesList[i]:“\0”;}138-15intFirstNeighbor(MGraph&G,intv){//给出顶点位置为v的第一个邻接顶点的位置if(v!=-1){for(intcol=0;colG.numVertices;col++)if(G.Edge[v][col]0&&G.Edge[v][col]maxValue)returncol;//顺序检测第v行寻找第一个邻接顶点//对于无权图，maxValue应为INT_MAX}return-1;}138-16intNextNeighbor(MGraph&G,intv,intw){//给出顶点v的某邻接顶点w的下一个邻接顶点intcol;if(v!=-1&&w!=-1){for(col=w+1;colG.numVertices;col++)if(Edge[v][col]0&&Edge[v][col]MaxValue)returncol;//在第v行顺序寻找下一个邻接顶点}return-1;}138-17邻接表(AdjacencyList)无向图的邻接表同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边（边结点）,结点中有另一顶点的下标dest和指针link。ABCDdataadjABCD0123destlinkdestlink130210138-18有向图的邻接表和逆邻接表ABCdataadjABC012destlinkdestlink邻接表(出边表)dataadjABC012destlink逆邻接表(入边表)102011138-19网络(带权图)的邻接表对于一个图来说，由于各边链入的顺序不同，邻接表表示是不惟一的。它适用于稀疏图。BACD69528dataadjABCD0123destcostlink1536283219(出边表)(顶点表)138-20带权图的边结点中保存该边上的权值cost。顶点i的边链表的表头指针adj在顶点表的下标为i的顶点记录中，该记录还保存了该顶点的其它信息。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。138-21邻接表表示的图的定义#definemaxVertices10//最大顶点个数#definemaxWeightFLT_MAXtypedefcharVType;//顶点数据类型typedefintWType;//边上权值类型typedefstructnode{//边结点intdest;//目标顶点下标WTypecost;//边上的权值Structnode*link;//下一边链接指针}EdgeNode;138-22typedefstructVertexNode{//顶点结点VTypedata;//顶点数据域structEdgeNode*first;//边链表头指针};typedefstructALGraph{//邻接表的结构定义VertexNodeVerticesList[maxVertices];//邻接表的静态存储结构intnumVerties,numEdges;//当前顶点数与边数};138-23WTypeGetWeight(ALGraph&G,intu,intv){//给出以顶点u和v为两端点的边上的权值if(u!=-1&&v!=-1){EdgeNode*p=G.VerticesList[u].firsr;while(p!=NULL){if(p-dest==v)returnp-cost;elsep=p-link;}}return0;}138-28邻接多重表(AdjacencyMultilist)在解决以边的处理为主的问题中，无论是邻接矩阵或邻接表，都有重复处理的麻烦。改进的办法就是使用邻接多重表，每一条边仅被表示一次。无向图的情形边结点的结构其中,mark是处理标记;vertex1和vertex2是该边两顶点位置。Path1指向下一条依附vertex1的边；path2指向下一条依附vertex2的边。markvertex1vertex2path1path2138-29对于带权图还需设置一个存放与该边相关的权值的域cost。顶点结点的结构存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，data存放与该顶点相关的信息，Firstout是指示第一条依附该顶点的边的指针。在邻接多重表中,所有依附同一个顶点的边都链接在同一个单链表中。dataFirstout138-30markvtx1vtx2path1path2010213e1e2e3dataFoutABCD0123e1e2e3ABCD从顶点i出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。邻接多重表结构图示138-31有向图的情形在用邻接表表示有向图时,有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表（十字链表）可把两个表结合起来表示。边结点的结构其中，mark是处理标记；vertex1和vertex2指明该有向边始顶点和终顶点的位置。Path1指向同一顶点发出的下一条边的边结点；path2指向进入同一顶点的下一条边的边结点。需要时还可有权值域cost。markvertex1vertex2path1path2138-32顶点结点的结构每个顶点有一个结点，它相当于出边表和入边表的头结点：其中，数据成员data存放与该顶点相关的信息，指针Firstout指示以该顶点为始顶点的出边表的第一条边，Firstin指示以该顶点为终顶点的入边表的第一条边。dataFirstinFirstout138-33markvtx1vtx2path1path2010312233440e1e2e3e4e5e6dataFinFoutABCDE01234e1e2e3e4e5e6ABCDE邻接多重表结构的图示138-34图的遍历与连通性从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(GraphTraversal)。北京大学版本的教材称遍历为“周游”。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被