图的表示及存储课件

单击此处编辑母版标题样式,a,单击此处编辑母版文本样式,a,第二级,a,第三级,a,第四级,a,第五级,*,1,基本图算法,陈嘉庆,1,基本概念和运算,2,1,基本概念和运算,3,1,基本概念和运算,4,图的基本概念,1,基本概念和运算,图,由,顶点集,V,和连接顶点的,弧集,E,所组成的结构，,记作,G = ( V, E ),。,其中,弧,的形式为,，,表示从顶点,Vi,到,Vj,之间有一条弧，图形表示为：,Vi Vj,-,有向图,例,：如右图中的,G1,就是一个有向图：,其中：,顶点集合,V=1,，,2,，,3,，,4,弧集,E= , , ,6,2,1,3,4,图,G1,有向图示例,1,基本概念和运算,如果顶点间的关系是相互的，,即弧的两端没有方向，则图为,无向图。,其中的弧称为,边。,边的,形式,为,(Vi,Vj),，,图形表示为：,Vi Vj,例,：如右图中的,G2,就是一个无向图：,其中：,顶点集合,V=1,，,2,，,3,，,4,边集,E=,（,1,2,）,（,1,3,）,（,1,4,）,（,2,4,）,（,3,4,）,7,2,1,3,4,图,G2,无向图示例,1,基本概念和运算,若,G,中每条边（弧）对应一个数值,表示关系的程度，则称图,G,为,网络,。,例,： 图,G3,就是一个网络,对图,G = ( V, E ),，若存在,G1=(V1,，,E1),，,满足,V1,V,，,E1,E,。则,G1,是,G,的,子图。,例如：,右图,G4,就是,G2,的子图。,8,2,1,3,4,6,5,8,3,7,图,G3,网络示例,2,1,3,4,图,G4,子图示例,2,1,3,4,图,G2,无向图示例,前三个图都是最后一个的子图。,1,基本概念和运算,顶点间关系,：,如果,E,则称,Vi,，,Vj,相邻接,，,Vi,邻接,到,Vj,，,Vj,邻接,自,Vi,。,例如，右 图中，,V1,邻接到,V2,，,V4,邻接自,V3,若,( Vi,Vj )E,则称,Vi,，,Vj,相邻接,或称,边,（,v1,，,v2,）,依附于,顶点,v1,和,v2,。,依附于某顶点的边数叫作该点的,度,.,9,2,1,3,4,图,G1,有向图示例,1,基本概念和运算,顶点的,度,顶点的邻接点的数目。,有向图中：,入度,，,出度,。,度入度出度,。,10,度是,2,例,2,4,5,1,3,6,G1,顶点,2,入度：,1,出度：,3,顶点,4,入度：,1,出度：,0,例,1,5,7,3,2,4,G2,6,顶点,5,的度：,3,顶点,2,的度：,4,度为,2,出度,1,1,基本概念和运算,路径,在无向图,G,中从顶点,v,p,到顶点,v,q,的,路径,是一个顶点序列（,v,p,v,i1,v,i2,.,，,v,in,v,q,），其中（,v,p, v,i1,）（,v,i1, v,i2,）,（,v,in, v,q,）是,E,（,G,）中的,边,。,图,G1,中，,1,2,4,1,3,4,是一条路径,路径长度,：称路径上边的数目为,路径长度,。,11,2,1,3,4,图,G1,有向图示例,2,到,4,的路径为,2-3-4,；长度为,2,1,基本概念和运算,简单路径,中间经过的顶点不重复的路径。,例,:,图,G1,中，,( 1,2,4 ) ( 1,3,4 ) ( 1,3,4,1 ),都是简单路径。,回路,首尾相同的路径。,例如，,( 1,3,4,1 ),简单回路,简单路径,+,回路,12,2,1,3,4,图,G1,有向图示例,1,基本概念和运算,若,无向图,中任意两点间都存在路径,则称为,连通图。,否则，称为,不连通图（非连通图）,。,非连通图包含若干,连通分量,-,极大连通子图。,13,1,2,5,3,4,连通图示例,6,7,1,2,5,3,4,非连通图示例,-,三个连通分量,连通图,连通,分量（强连通分量）,无向图,G,的极大连通子图称为,G,的连通分量,极大连通子图指：该子图是,G,连通子图，将,G,的任何不在该子图中的顶点加入，子图不再连通。,非连通图,连通分量,V1,V3,V4,V2,V6,V5,V1,V3,V2,非连通分量,1,基本概念和运算,有向图,D,的极大强连通子图称为,D,的强连通分量,极大强连通子图指：该子图是,D,强连通子图，将,D,的任何不在该子图中的顶点加入，子图不再是强连通的。,强连通分量,V1,V2,V3,V4,V1,V3,V4,V2,1,基本概念和运算,1,基本概念和运算,若,有向图,中的任意两点间可以,互相到达,则称为,强连通图。,16,6,7,1,2,5,3,4,强连通图示例,强连通图,V1,V2,V3,V4,非强连通图,V1,V2,V3,V4,若加上这条线就成强连通图了,【,练习,】,：,【,问,】,：,n,个顶点的连通图至少有几条边？强连通图呢？,【,答,】,：,n,个顶点的连通图至少有,n-1,条边，它们构成一棵树。,n,个顶点的强连通图至少有,n,条边，它们构成首尾相连的有向环。,1,基本概念和运算,1,基本概念和运算,若,无向图,中任意两点间都有一条边,则称为,无向完全图。,（共有,n (n-1) / 2,条边）,若,有向图,中每个顶点到其余各点均有一条弧,则称为,有向完全图。,（共有,n (n-1),条边）,18,1,2,5,3,4,5,阶无向完全图,2,1,3,4,4,阶有向图示例,1,基本概念和运算,若无向图满足：,连通并且无回路,则称为,树。,树的定义有如下几个,等价的描述,：,有最少边数的连通图。,有,n-1,条边的连通图。,连通的无环图。,有向树,如果在有向图中，,有一个顶点的入度为,0,，其余顶点的入度为,1,，,则称此图为有向树。,并称其中入度为,0,的顶点为,有向根,。,右下图就是一个有向树，其中顶点,1,就是有向根。,19,6,7,1,2,5,3,4,树的示例,6,7,1,2,5,3,4,有向树示例,网,：在图,G,中，若图的边带有,权值,，比如图的边上有表示从一个顶点到另一个顶点的距离或是花费，则称,G,为,网,或,网络,。,1,基本概念和运算,图的存储,1,、数组表示法,（邻接矩阵表示）,在图的邻接矩阵表示中，有一个,记录各个顶点信息,的,顶点表,，还有一个,表示各个顶点之间关系,的,邻接矩阵,。,设图,A = (V, R),是一个有,n,个顶点的图，则图的邻接矩阵是一个二维数组,Matrixnn,，定义：,2,图的存储,2,图的存储,图的,存储,-,图结构在计算机中的存储形式,1,。邻接矩阵,（,1,）,不带权值,假设图中有,n,个顶点。则采用,nn,的矩阵,A,来表示，,1 E,其中,A,ij,0,否则,例,：,23,1,3,2,4,0 1 1 0,0 0 0 1,0 0 0 1,1 0 0 0,行的方向：发出的弧,列的方向 ：进入的弧,对应关系,2,1,4,3,5,无向图,的邻接矩阵,B,A,D,C,E,有向图,的邻接矩阵,2,图的存储,（,2,）,网络,的表示方法,w,ij,E,A,ij,0,或,否则,例,：,26,4 3 5,4,2,3,6,5 2 6,1,2,4,3,0 1 1 1,1 0 0 1,1 0 0 1,1 1 1 0,无向图,的邻接矩阵,对称,1,4,2,3,6,3,5,2,4,特点：,(1),无向图邻接矩阵是对称矩阵，同一条边表示了两次；,(2),顶点,v,的度：等于二维数组对应行（或列）中,1,的个数；,(3),判断两顶点,v,、,u,是否为邻接点：只需判二维数组对应分量是否为,1,；,(4),顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值,1,或清,0,；,2,图的存储,2.,邻接表表示法,-,将 邻接点构成链表,例,：,1,2,3,4,2,27,1,2,4,3,data,firstadj,3,4,1,4,1,4,1,2,3,对应关系,2,图的存储,逆邻接链表,-,将“邻接自”的顶点连成链表,1,2,3,4,4,28,data firstadj,1,1,3,4,3,2,1,3,2,1,2,3,4,data,firstadj,4,4,1,2,data firstadj,对应关系,代表弧,【,练习,】,：,【,问,】,：给定有向图,G=(V,E),的邻接链表，需要多长时间 才能计算出每个结点的出度？,多长时间才能计算出每个结点的入度？,【,答,】,：,计算出度的时间：,E,计算入度的时间：,E,2,图的存储,【,练习,】,：,请编写建立图的,邻接矩阵,的参考,程序段,【,答,】,：建立邻接矩阵时，有两个小技巧：,初始化数组,大可不必使用两重循环,（,1,）如果是,Longint,数组,，采用,fillchar(g,sizeof(g),$7f),可全部初始化为,maxlongint,使用,fillchar(g,sizeof(g),0),全部清为,0,。,(2),如果是,Real,数组,，采用,fillchar(g,sizeof(g),127),可全部初始化为一个很大的数,1.38*10,306,，使用,ficllchar(g,sizeof(g),0),全部清为,0.,2,图的存储,【,图的邻接矩阵,】,：参考程序段,#include,using namespace std;,int i,j,k,e,n;,double g101101;,double w;,int main(),int i,j;,for (i = 1; i = n; i+),for (j = 1; j e;,for (k = 1; k i j w;,/读入两个顶点序号及权值,gij = w;,/对于不带权的图gij=1,gji = w;,/无向图的对称性,如果是有向图则不要有这句！,return 0;,2,图的存储,Pascal,程序代码段请参看,Free Pascal,语言与算法基础,398,页,【,练习,】,：,请用数组模拟,邻接表,的方式建立图,图的,邻接表存储法,，又叫,链式存储法,。本来是要采用,链表,实现的，但大多数情况下只要用,数组模拟,即可。,定义两个数组，例如：int g101101;用来存储这个图。再定义一个一维数组：,int num101;用来记录与每个点相连的点的数目。,如果边有权值，还要定义一个数组int val101101存储边权。,2,图的存储,在,C+,语言中可用,STL,链表实现链表维护,【,数组模拟邻接表存储,】,：参考程序段,#include,using namespace std;,int n,m,i,j,c;,int g101101;,int num101;,int main(),memset(g,0x7f,sizeof(g);,memset(num,0,sizeof(num);,cinn;,for (i = 1; i numi;,/第i行说明点i的连接情况，每行的开头读入与之相连的点的数目,for (j = 1; j gij,; /第j个与i相连的点是gij,vali gij = v,; /有权图还要存下权值,return 0;,2,图的存储,Pascal,程序代码段请参看,Free Pascal,语言与算法基础,399,页,2,图的存储,在,邻接表,中，添加一条边的时间复杂度为,O(1),，无向图要存,2,次。,遍历单个节点连边的时间复杂度为,O,（,V)-,该点所连的边数,查询两个节点间是否可达，只能遍历所有这个节点的链表，时间复杂度为,O,（,V)-,该点所连的边数,保存图的空间复杂度，粗略估计为,O,（,V,）,-,总边数,邻接矩阵中，添加一条边的时间复杂度为,O(1),查询两个节点间是否可达，邻接矩阵时间复杂度为,O(1),，直接访问即可,邻接矩阵的内存复杂度为,O,（,n,2,),34,35,谢谢！,