数据结构图

第8章图图的基本概念图的存储结构邻接矩阵图类的实现图的遍历最小生成树最短路径拓扑排序关键路径主要知识点8.1图8.1.1.图的基本概念图是由顶点（或称结点）集合及顶点间的关系集合组成的一种数据结构。图G的定义是：G=（V，E）其中，V={x|x∈某个数据元素集合}E={(x，y)|x，y∈V}或E={＜x，y＞|x，y∈V并且Path(x，y)}其中，（x，y）表示从x到y的一条双向通路，即（x，y）是无方向的；Path（x，y）表示从x到y的一条单向通路，即Path（x，y）是有方向的。问题：图的特点图有许多复杂结构，本课程只讨论最基本的图，因此，本章讨论的图中不包括从自身到自身的边存在的图，以及带自身环的图BCAABCD(a)(b)基本术语：（1）顶点结点（）和边：图中的结点也称作顶点，图中的第i个顶点记做vi。两个顶点vi和vj相关联称作顶点vi和vj之间有一条边，图中的第k条边记做ek，ek=（vi,vj）或＜vi,vj＞。（2）有向图和无向图：在有向图中，顶点对＜x,y＞是有序的，顶点对＜x,y＞称为从顶点x到顶点y的一条有向边，有向图中的边也称作弧；在无向图中，顶点对（x,y）是无序的，顶点对（x,y）称为与顶点x和顶点y相关联的一条边。（3）完全图：在有n个顶点的无向图中，若有n(n-1)/2条边，即任意两个顶点之间有且只有一条边，则称此图为无向完全图；在有n个顶点的有向图中，若有n(n-1)条边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为有向完全图。（4）邻接顶点：在无向图G中，若（u,v）是E(G)中的一条边，则称u和v互为邻接顶点，并称边（u,v）依附于顶点u和v；在有向图G中，若＜u,v＞是E(G)中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边＜u,v＞和顶点u和顶点v相关联。。013201234560120123(a)(b)(c)(d)（5）顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。顶点的度=入度+出度。（6）路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径（7）权：有些图的边附带有数据信息，这些附带的数据信息称为权。带权的图也称作网络或网。（8）路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。（9）子图：设有图G1={V1,E1}和图G2={V2,E2}，若V1V2，且E1E2，则称图G2是图G1的子图。2135467879610612715163BACDE60304575804035施工进度图交通网络图（10）连通图和强连通图：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。在有向图中，若对于任意一对顶点vi和顶点vj（vi≠vj）都存在路径，则称图G是强连通图。（11）生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。生成树一般是对无向图来讨论。（12）简单路径和回路：若路径上各顶点v1,v2,…,vm,互不重复，则称这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。数据集合：由一组顶点集合{vi}和一组边{ej}集合组成。当为带权图时每条边上权wj还构成权集合{wj}。操作集合：（1）初始化（2）插入结点：在某个位置插入一个结点（3）插入边：在某个位置插入一条边（4）删除边：删除某个位置的一条边（5）删除结点：删除某个位置的一个结点（6）第一个邻接顶点：在图中寻找某结点的第一个邻接结点（7）下一个邻接顶点：在图中寻找某结点的邻接结点的下一个邻接结点（8）遍历：遍历图中的每一个结点且每个结点只被遍历一次。8.1.2.图的抽象数据类型8.2图的存储结构图的存储结构主要有邻接矩阵和邻接表两种。8.2.1.图的邻接矩阵存储结构否则或若0,),(1EvvEvvajijiij假设图G=(V,E)有n个顶点，即V={v0,v1,…,vn-1}，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足：由于矩阵A中的元素aij表示了顶点vi和顶点vj之间边的关系，或者说，A中的元素aij表示了顶点vi和顶点vj（0≤j≤n-1）的邻接关系，所以矩阵A称作邻接矩阵。无向图的邻接矩阵一定是对称矩阵2143554321V0010100011100010100111110A(b)(a)有向图的邻接矩阵一般是非对称矩阵其中V表示了图的顶点集合，A表示了图的邻接矩阵BADCEEDCBAV0000000010100000000011110A(b)(a)214356080070807005040500304002030200A654321V(a)(b)402030507080带权图及其邻接矩阵其中V表示了图的顶点集合，A表示了图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0aij∞的元素个数等于第i个顶点的出度，邻接矩阵第j列中所有0aij∞的元素个数等于第j个顶点的入度。8.2.2.图的邻接表存储结构当图的边数少于顶点个数且顶点个数值较大时，图的邻接n×n矩阵的存储问题就变成了稀疏矩阵的存储问题，此时，邻接表就是一种较邻接矩阵更为有效的存储结构。BADCE(a)01234ABCDE0datasorce1432adjdestnext23411∧∧∧∧(b)4∧数组的data域存储图的顶点信息，sorce域存储该顶点在数组中的下标序号，adj域为该顶点的邻接顶点单链表的头指针。第i行单链表中的dest域存储所有起始顶点为vi的邻接顶点vj在数组中的下标序号，next域为单链表中下一个邻接顶点的指针域。如果是带权图，单链表中需再增加cost域，用来存储边vi,vj的权值wij。问题：邻接表存储结构和数组一章中的什么存储结构类似？8.3邻接矩阵图类1.邻接矩阵图类AdjMWGraph的设计publicclassAdjMWGraph{staticfinalintmaxWeight=10000;privateSeqListvertices;//存储结点的顺序表privateint[][]edge;//存储边的二维数组privateintnumOfEdges;//边的个数publicAdjMWGraph(intmaxV){//构造函数，maxV为结点个数vertices=newSeqList(maxV);edge=newint[maxV][maxV];for(inti=0;imaxV;i++){for(intj=0;jmaxV;j++){if(i==j)edge[i][j]=0;elseedge[i][j]=maxWeight;}}numOfEdges=0;}publicintgetNumOfVertices(){//返回结点个数returnvertices.size;}publicintgetNumOfEdges(){//返回边的个数returnnumOfEdges;}publicObjectgetValue(intv)throwsException{//返回数据元素returnvertices.getData(v);}publicintgetWeight(intv1,intv2)throwsException{//返回权值if(v10||v1=vertices.size||v20||v2=vertices.size)thrownewException(参数v1或v2越界出错！);returnedge[v1][v2];}publicvoidinsertVertex(Objectvertex)throwsException{//插入结点vertices.insert(vertices.size,vertex);//调用顺序表的插入函数}publicvoidinsertEdge(intv1,intv2,intweight)throwsException{//插入边v1,v2，权值为weightif(v10||v1=vertices.size||v20||v2=vertices.size)thrownewException(参数v1或v2越界出错！);edge[v1][v2]=weight;//置边的权值numOfEdges++;//边的个数加1}publicvoiddeleteEdge(intv1,intv2)throwsException{//删除边if(v10||v1vertices.size||v20||v2vertices.size)thrownewException(参数v1或v2越界出错！);if(edge[v1][v2]==maxWeight||v1==v2)thrownewException(该边不存在！);edge[v1][v2]=maxWeight;//置边的权值为无穷大numOfEdges--;//边的个数减1}publicintgetFirstNeighbor(intv)throwsException{//取第一个邻接点if(v0||v=vertices.size)thrownewException(参数v越界出错！);for(intcol=0;colvertices.size;col++)if(edge[v][col]0&&edge[v][col]maxWeight)returncol;return-1;}publicintgetNextNeighbor(intv1,intv2)throwsException{//取结点v1的邻接结点v2后的邻接结点if(v10||v1=vertices.size||v20||v2=vertices.size)thrownewException(参数v1或v2越界出错！);for(intcol=v2+1;colvertices.size;col++)if(edge[v1][col]0&&edge[v1][col]maxWeight)returncol;return-1;}}2.邻接矩阵图类AdjMWGraph的测试例8-1以图8-8所示的带权有向图为例，编写测试邻接矩阵图类的程序ABCDE1040305020publicclassRowColWeight{introw;//行下标intcol;//列下标intweight;//权值publicRowColWeight(intr,intc,intw){//构造函数row=r;col=c;weight=w;}publicstaticvoidcreateGraph(AdjMWGraphg,Object[]v,intn,RowColWeight[]rc,inte)throwsException{for(inti=0;in;i++)g.insertVertex(v[i]);for(intk=0;ke;k++)g.insertEdge(rc[k].row,rc[k].col,rc[k].weight);}}publicclassExam8_1{publicstaticvoidmain(String[]args){intn=5,e=5;AdjMWGraphg=newAdjMWGraph(n);Character[]a={newCharacter('A'),newCharacter('B'),newCharacter('C'),newCharacter('D'),newCharacter('E')};RowCol