7-数据结构与算法-北京大学2008-张铭-图

数据结构与算法第7章图本章由王腾蛟主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。主要内容7.1图的定义和术语7.2图的抽象数据类型7.3图的存储结构7.4图的周游7.5最短路径7.6最小生成树7.7图知识点总结“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语图(Graph)由表示数据元素的集合V和表示数据之间关系的集合E组成，记为G=V，E在图中，数据元素通常称作顶点(vertex)，V就是顶点的有穷非空集合顶点的序偶，称之为边(edge)，E是边的集合有向图、带权图、稀疏图、稠密图、完全图、连通图“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语若代表一条边的顶点序偶是无序的(即该边无方向)，则称此图为无向图。若代表一条边的顶点序偶是有序的(即边有方向)，则称此图为有向图。图7.2图的示例v0v2v3v1v4v0v2v1v3(a)无向图G1(b)有向图G2“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语通常用n表示图中顶点的数目，用e表示边或弧的数目。无向图中e的取值范围是从0到n(n-1)/2，有向图中e的取值范围是从0到n(n-1)边数相对较少的图称为稀疏图(sparsegraph)边数相对较多的图称为稠密图(densegraph)任何两顶点间都有边相关联的图称为完全图(completegraph)，完全图显然具有最大的边数“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语ABCACBDABCACBD（a）无向完全图（b）有向完全图图7.3完全图“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语设G=V,E是一个图，若E′是E的子集，V′是V的子集，且E′中的边仅与V′中顶点相关联，则图G′=(V′,E′)称为图G的子图(subgraph)。v0v0v2v3v1v4v0v2v3v0v1v3（a）无向图G1的若干子图（b）有向图G2的若干子图图7.4图7.2的若干子图“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语无向图G=V,E中从顶点vp到顶点vq的路径(path)是一个顶点序列(vp=vi0，vi1，vi2，…，vim=vq)，其中(vij-1，vij)∈E，1≤j≤m。若G是有向图，则路径也是有向的，顶点序列应满足vij-1，vij∈E，1≤j≤m路径长度(length)定义为路径上的边（或弧）的数目第一个顶点和最后一个顶点相同的路径称为回路或环(cycle)序列中顶点不重复出现的路径称为简单路径(simplepath)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语除了第一个顶点和最后一个顶点外，其余顶点不重复的回路，称为简单回路(simplecycle)不带回路的图称为无环图(acyclicgraph)不带回路的有向图称为有向无环图(directedacyclicgraph，简记为DAG)一个有向图中，若存在一个顶点v0，从此顶点有路径可以到达图中其他所有顶点，则称此有向图为有根的图，v0称作图的根“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj是连通的(connected)。如果对于图中的任意两个顶点vi,vj∈V，vi和vj都是连通的，则称无向图G为连通图。连通分量(connectedcomponent)定义为无向图中的极大连通子图。v0v2v1v3v5v6v7v8v4v0v2v1v3v5v6v7v8v4(a)非连通的无向图G3（b）非连通无向图G3的连通分量图7.5非连通无向图的连通分量示意图“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语对于有向图G=V，E，若G中任意两个顶点vi和vj(vi≠vj)，都有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称有向图G是强连通图。有向图强连通的极大子图称为该有向图的强连通分支或者强连通分量。图7.6有向图G2的两个强连通分量v0v2v3v1“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.1图的定义和术语一个连通图的生成树是含有该连通图全部顶点的一个极小连通子图。若连通图G的顶点个数为n，则G的生成树的边数为n-1。但是有n-1条边的图不一定是生成树。如果无向图G的一个生成树G′上添加一条边，则G′中一定有环，因为依附于这条边的两个顶点有另一条路径。相反，如果G′的边数小于n-1，则G′一定不连通。图7.7图7.2中无向图和有向图的生成树示例v0v2v3v1v4v0v2v1v3(a)无向图G1的生成树(b)有向图G2的生成树图7.2图的示例v0v2v3v1v4v0v2v1v3(a)无向图G1(b)有向图G2“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.2图的抽象数据类型自由树(freetree)是不带简单回路的无向图，它是连通的，并且具有n-1条边。网络(network)是带权的连通图，图7.8中的G4是一个网络。如果一个有向图只有一个顶点的入度为0，其余顶点的入度均为1，则称为有向树。一个有向图的生成森林由若干棵有向树组成，这些树的并集包含了原图所有顶点，各有向树的弧不相交。图7.9就是有向图生成森林的示例。v0v1v2v3341569v0v2v3v1v4v5v0v1v3v4v2v5（a）有向图（b）有向图的生成森林图7.8网络实例G4图7.9有向图及其生成森林“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.2图的抽象数据类型【代码7.1】图的抽象数据类型classGraph{//图的ADTpublic:intVerticesNum();//返回图的顶点个数intEdgesNum();//返回图的边数//返回与顶点oneVertex相关联的第一条边EdgeFirstEdge(intoneVertex);//返回与边PreEdge有相同关联顶点oneVertex的//下一条边EdgeNextEdge(EdgepreEdge);“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.2图的抽象数据类型//添加一条边boolsetEdge(intfromVertex,inttoVertex,intweight);//删一条边booldelEdge(intfromVertex,inttoVertex);//如果oneEdge是边则返回TRUE，否则返回FALSEboolIsEdge(EdgeoneEdge);“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.2图的抽象数据类型//返回边oneEdge的始点intFromVertex(EdgeoneEdge);//返回边oneEdge的终点intToVertex(EdgeoneEdge);//返回边oneEdge的权intWeight(EdgeoneEdge);};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.3图的存储结构7.3.1相邻矩阵7.3.2邻接表7.3.3十字链表“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.3.1相邻矩阵图的相邻矩阵(adjacencymatrix，或邻接矩阵)表示顶点之间的邻接关系，即表示顶点之间有边或没有边的情况。设G=V，E是一个有n个顶点的图，则图的相邻矩阵是一个二维数组A[n，n]，定义如下：1EEA[ij]=0EEijijijij，若(V，V)或V，V，，若(V，V)或V，V对于n个顶点的图，相邻矩阵的空间代价都为O(n2)，与边数无关。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.3.1相邻矩阵【代码7.2】图的基类classEdge{//边类public:intfrom,to,weight;//from是边的始点,to是终点,weight是边的权Edge(){//缺省构造函数from=-1;to=-1;weight=0;}Edge(intf,intt,intw){//给定参数的构造函数from=f;to=t;weight=w;}};classGraph{public:intnumVertex;//图中顶点的个数intnumEdge;//图中边的条数int*Mark;//标记图的顶点是否被访问过int*Indegree;//存放图中顶点的入度Graph(intnumVert){//图的构造函数numVertex=numVert;numEdge=0;“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.3.1相邻矩阵Indegree=newint[numVertex];Mark=newint[numVertex];for(inti=0;inumVertex;i++){Mark[i]=UNVISITED;//标志位设为UNVISITEDIndegree[i]=0;//入度设为0}}~Graph(){//析构函数delete[]Mark;//释放Mark数组delete[]Indegree;//释放Indegree数组}intVerticesNum(){//返回图中顶点的个数returnnumVertex;}boolIsEdge(EdgeoneEdge){//oneEdge是否是边if(oneEdge.weight0&&oneEdge.weightINFINITY&&oneEdge.to=0)returntrue;elsereturnfalse;}};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.3.2邻接表当图中的边数较少时，相邻矩阵就会出现大量的零元素，存储这些零元素将耗费大量的存储空间。对于稀疏图，可以采用邻接表存储法。邻接表(adjacencylist)表示法是一种链式存储结构，由一个顺序存储的顶点表和n个链接存储的边表组成。顶点表目有两个域：顶点数据域和指向此顶点边表指针域边表把依附于同一个顶点vi的边（即相邻矩阵中同一行的非0元素）组织成一个单链表。边表中的每一个表目都代表一条边，由两个主要的域组成：•与顶点vi邻接的另一顶点的序号•指向边表中下一个边表目的指针“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.3.2邻接表顶点结点和边（或弧）结点的结构如下所示：datafirstarc顶点结点adjvexnextarc边（或弧）结点Info“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。7.3.2邻接表假设（vi，vj）是无向图中的一条边，在顶点vi的边表里存储有边（vi，vj）对应的边结点，在顶点vj