图的基本概念和存储结构课件.ppt

1、图和图的存储结构图和图的存储结构 图的定义和术语图的定义和术语 图的存储表示图的存储表示 小结小结用用java语言描述图的存储结构语言描述图的存储结构 课堂练习课堂练习1.图的定义图的定义2.图的名词和术语图的名词和术语3.图的基本操作图的基本操作图和图的存储结构图和图的存储结构图的定义图的定义 图(graph)是由一个顶点(vertex)集 V 和一个边(edge|弧arc)集 E构成的数据结构。Graph=(V,E)E(v,w|v,wV)每条边(edge)是一副点对(v,w)，其中v,w V。表示从 v 到 w 的一条边(弧)，称 v 为弧尾(tail)，w 为弧头(head)。图的定义图

2、的定义有向图有向图 如果“弧”是有方向的，则称由顶点集和弧集构成的图为有向图有向图(digraph)。EACBD例如例如:G1=(V1,E1)V1=A,B,C,D,EE1=,图的定义图的定义无向图无向图若若 E 必有必有 E,则以无序对则以无序对(v,w)代替这两个有序对，称代替这两个有序对，称 (v,w)为顶点为顶点 v 和顶和顶点点 w 之间存在一条边。之间存在一条边。上述这种由顶点集和边集构成的图称作上述这种由顶点集和边集构成的图称作无向图无向图。图的定义图的定义无向图无向图例如例如:G2=(V2,E2)BCAFEDV2=A,B,C,D,E,FE2=(A,B),(A,E),(B,E),(

3、B,F),(C,D),(C,F)(D,F弧除了有向和无向的含义之外，有时候还具有弧除了有向和无向的含义之外，有时候还具有第三种成分，称为权第三种成分，称为权(weight)或值或值(cost)。名词和术语名词和术语1 1）子图、网子图、网 2 2）完全图、稀疏图、稠密图完全图、稀疏图、稠密图3 3）邻接点、度、入度、出度邻接点、度、入度、出度4 4）路径、路径长度、简单路径、简单回路路径、路径长度、简单路径、简单回路5 5）连通图、强连通图、弱连通图连通图、强连通图、弱连通图1）子图、网 设图G=(V,E)和图 G=(V,E),且 VV,EE,则称 G 为 G 的子图。EACBDEACBDB名

4、词和术语名词和术语弧或边带权的图分别称作有向网或无向网。ABECD1597211132名词和术语名词和术语1）子图、网 2）完全图、稀疏图、稠密图假设图中有 n 个顶点，e 条边，则含有 e=n(n-1)/2 条边的无向图称作完全图;含有 e=n(n-1)条弧的有向图称作有向完全图;若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。名词和术语名词和术语3）邻接点、度、入度、出度邻接点：假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，度：和顶点v关联的边的数目，记为TD（v）。边(v,w)和顶点v和w相关联。名词和术语名词和术语ACDFEBTD(B)=3TD(A)=23）邻

5、接点、度、入度、出度ABECD顶点的出度:以顶点v 为弧尾的弧的数目;记为OD（v）对于右图所示的有向图来说，由于弧有方向性，则有入度和出度之分。名词和术语名词和术语3）邻接点、度、入度、出度顶点的入度:以顶点v为弧头的弧的数目，记为ID（v）顶点的度(TD)=出度(OD)+入度(ID)ID(B)=2OD(B)=1TD(B)=3名词和术语名词和术语ABECDID(A)=1OD(A)=2TD(A)=33）邻接点、度、入度、出度名词和术语名词和术语ABECD在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2 B.1 C.2 D.4ACDFEB思考思考ABECD4）路径、路径长度、简单路

6、径、简单回路、圈(环)路径：设图G=(V,E)中的一个顶点序列u=v1,v2,vN=w中，(vi,vi+1)E，0iN，则称从顶点u 到顶点w 之间存在一条路径。如:从A到D长度为 3 的路径A,B,C,D名词和术语名词和术语路径长度：路径上边的数目。简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同的路径。名词和术语名词和术语圈(cycle):是满足v1=vN且长至少为1的一条路径。如果该路径是简单路径，那么这个圈就是简单圈。一个有向无圈图简称为DAG。ABECD4）路径、路径长度、简单路径、简单回路、圈(环)5）连通图、强连通图、弱连通图连通图：若无向图

7、G中任意两个顶点之间都有路径相通，则称此图为连通图;BACDFE名词和术语名词和术语强连通图：若有向图任意两个顶点之间都存在一条有向路径，则称为强连通图。ABECD名词和术语名词和术语若有向图去掉弧的方向后是连通的，则称为弱连通图。5）连通图、强连通图、弱连通图基本操作基本操作1.结构的建立和销毁结构的建立和销毁3.插入或删除顶点插入或删除顶点5.对邻接点的操作对邻接点的操作2.对顶点的访问操作对顶点的访问操作6.遍历遍历4.插入和删除弧插入和删除弧CreatGraph(V,E):/按定义(V,E)构造图DestroyGraph(G):/销毁图1.结构的建立和销毁结构的建立和销毁基本操作基本操

8、作2.对顶点的访问操作对顶点的访问操作LocateVex(u);/若G中存在顶点u，则返回该顶点在/图中“位置位置”；否则返回其它信息。GetVex(v);/返回 v 的值。PutVex(v,value);/对 v 赋值value。基本操作基本操作3.插入或删除顶点插入或删除顶点InsertVex(v);/在图G中增添新顶点v。DeleteVex(v);/删除G中顶点v及其相关的弧。基本操作基本操作4.插入和删除弧插入和删除弧InsertArc(v,w);/在G中增添弧，若G是无向的，/则还增添对称弧。DeleteArc(v,w);/在G中删除弧，若G是无向的，/则还删除对称弧。基本操作基本操

9、作5.对邻接点的操作对邻接点的操作FirstAdjVex(v);/返回 v 的“第一个邻接点第一个邻接点”。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(v,w);/返回 v 的（相对于 w 的）“下一个邻接下一个邻接 点点”。/若 w 是 v 的最后一个邻接点，则返回“空”。基本操作基本操作6.6.遍历遍历DFSTraverse(G,v);/从顶点v起深度优先深度优先遍历图G。BFSTraverse(G,v);/从顶点v起广度优先广度优先遍历图G。基本操作基本操作一、一、图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示二、二、图的邻接表存储表示图的邻接表存储表示图的

10、存储表示图的存储表示三、三、存储结构的比较存储结构的比较图的存储表示图的存储表示-邻接矩阵1325674邻接矩阵(adjacent matrix)表示法：使用一个二维数组，对于每一条边(u,v)，置Auv=true；否则，为false。如果边有一个权，可以置Auv等于该权，而使用一个很大或者很小的权作为标记表示不存在的边。图的存储表示图的存储表示-邻接矩阵1 2 3 4 5 6 7 1325674tttttttttttt1234567图的存储表示图的存储表示-邻接矩阵BACDFE无向图：对称矩阵无向图：对称矩阵ABCDEFABCDEF0 1 0 0 1 0 1 0 0 0 1 1 0 0 0

11、1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 l对于稠密(dense)图合适。图的存储表示图的存储表示-邻接表邻接表(adjacency list)表示法：对每一个顶点，使用一个表存放所有邻接的顶点。如果边有权，那么这个附加信息也可以存储在邻接表中。1325674图的存储表示图的存储表示-邻接表12345672,3,44,563,6,74,7(empty)6l对于稀疏(sparse)图合适。这种邻接表本身可以被保存在任何种类的List中。ArrayList和LinkedList。1325674图的存储表示图的存储表示-邻接表邻接表：图的链式存储结构邻接表：

12、图的链式存储结构对图中每个顶点建立一个单链表，第对图中每个顶点建立一个单链表，第i个单链个单链表中的节点表示依附顶点表中的节点表示依附顶点Vi的边。的边。对有向图来说，是指以顶点对有向图来说，是指以顶点Vi为弧尾的弧。为弧尾的弧。图的存储表示图的存储表示-邻接表012345ABCDEF14043525011253BACDFE1）无向图的邻接表）无向图的邻接表图的存储表示图的存储表示-邻接表ABECD01234ABCDE14301222）有向图的邻接表）有向图的邻接表-每个顶点链接的是以该顶点为每个顶点链接的是以该顶点为弧尾的弧弧尾的弧但，在有向图的邻接表中不易找到指向该顶点的弧。但，在有向图的

13、邻接表中不易找到指向该顶点的弧。图的存储表示图的存储表示-邻接表ABECD3）有向图的逆邻接表）有向图的逆邻接表-每个顶点链接的是指向该每个顶点链接的是指向该顶点的弧顶点的弧0101234ABCDE32034图的存储表示图的存储表示-邻接表邻接表：图的链式存储结构邻接表：图的链式存储结构adjvex nextarcinfo邻接点域邻接点域链域链域数据域（存放权值等）数据域（存放权值等）datafirstarc数据域数据域指向链表中第一个节点指向链表中第一个节点弧节点类弧节点类(链表节点类链表节点类)：顶点节点类顶点节点类：0101234ABCDE32034firstarc,弧节点类都属于链表的

14、Node类。图的存储表示图的存储表示-邻接表0101234ABCDE32034public class Vertex AnyType data;Arc firstArc;/boolean visited;public class Arcint adjVex;Arc nextArc;/int weight;图的存储表示图的存储表示-邻接表图的邻接表：1、容易找到任意顶点的一个邻接点2、但是要判定任意两个顶点（vi，vj）之间是否有边或者弧相连，需要搜索第i个或者第j个链表，不如邻接矩阵方便。存储结构的比较存储结构的比较邻接矩阵可用于DG、UDG、DN、UDN邻接表可用于DG、UDG、DN、UDN

15、一、应用范围存储结构的比较存储结构的比较邻接矩阵:n+n2邻接表用于DG和DN：n+e或者n+2e；用于UDG和UDN：n+2e二、存储空间存储结构的比较存储结构的比较三、对操作的支持1、对顶点的访问locateVex(u);/返回u的位置getVex(v);/返回 v 的值。putVex(u,value);/对 u 赋值value。存储结构的比较存储结构的比较2、插入和删除顶点都是对存放顶点数组元素的操作但是对邻接矩阵，还要修改邻接矩阵insertVex(v);/在图G中增添新顶点v。deleteVex(v);/删除G中顶点v及其相关的弧。存储结构的比较存储结构的比较3、插入和删除弧inse

16、rtArc(v,w);deleteArc(v,w);邻接矩阵：修改边（以及）邻接表：无向图，修改两个顶点的链表；有向图，修改一个（或两个）顶点的链表存储结构的比较存储结构的比较4、邻接点firstAdjVex(v);/返回 v 的“第一个邻接点第一个邻接点”。若没有邻接点，则返回-1。nextAdjVex(v,w);/返回 v 的（相对于 w 的）“下一个邻接下一个邻接 点点”。若 w 是 v 的最后一个邻接点，则返回-1。存储结构的比较存储结构的比较邻接矩阵：第v行邻接表：第v个链表5、邻接边课堂练习课堂练习V1V2V3V4V51、邻接矩阵2、邻接表V2V1V4V31、邻接矩阵2、邻接表课堂

17、练习课堂练习下面关于图的存储的叙述中正确的是（）A）用相邻矩阵法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关 B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关 C）用邻接表法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关 D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关 课堂练习课堂练习用用javajava语言描述存储结构语言描述存储结构1 1、邻接点函数的实现邻接点函数的实现2 2、创建图创建图3 3、图的存储方式的转换图的存储方式的转换(自学自学)邻接点函数的实现邻接点函数的实现012345ABCDEF14

18、043525011253firstAdjVex(A)firstAdjVex(B)nextAdjVex(A,1);nextAdjVex(B,4);邻接点函数的实现邻接点函数的实现int firstAdjVex(int v)Arc p;p=vertexsv.firstarc;/v的第1个邻接点 if(p=null)return-1;/无邻接点 return p.adjvex;邻接点函数的实现邻接点函数的实现int nextAdjVex(int v,int w)Arc p=vertexsv.firstArc;/v的第1个邻接点 while(p!=null&p.adjVex!=w)p=p.nextAr

19、c;if(p!=null)p=p.nextArc;/w之后的下一个邻接点 if(p!=null)return p.adjVex;else return-1;创建图创建图BACDFE输入边形式1：.输入边形式2：.输入顶点：A B C 1、图的两个个参数：顶点个数边数（弧数）vertex(Vertices)，vexNumedge(arc)，arcNum，edgeNum2、图的第三个参数：图的类型graphKind=DG,UDG,DN,UDN创建图创建图1、输入参数:vexNum,arcNum,graghKind2、输入顶点信息3、根据GraghKind，决定边是否要带权重4、采用某种形式逐条输入

20、边，将它插入到存储结构中建立存储结构的一般步骤：创建图创建图void createGragh()/建立邻接表/输入顶点数vexNum，边的条数arcNum，图的类型graghKind。if switch(graghKind)case DG:return CreateDG();case DN:return CreateDN();case UDG:return CreateUDG();case UDN:return CreateUDN();default:return ERROR;创建图创建图void createDG()for(i=0;ivexNum;i+)/输入顶点信息,data为输入的顶点数

21、据verticesi.data=data for(i=0;iarcNum;i+)/输入边的信息,为输入的弧信息p=new arcNode;/建立节点if(!p)return ERROR;p.adjVex=w;p.nextArc=verticesv.firstarc;/顶点v的链表verticesv.firstArc=p;/添加到最左边 创建图创建图void createUDG()for(i=0;ivexNum;i+)/输入顶点信息,data为输入的顶点数据verticesi.data=data 创建图创建图public void addEdge(int start,int end)Arc p=

22、new Arc(end);p.nextArc=vertexsstart.firstArc;vertexsstart.firstArc=p;Arc q=new Arc(start);q.nextArc=vertexsend.firstArc;vertexsend.firstArc=q;时间复杂度分析(第2种输入形式)第1个for:n第2个for:e所以O(n+e)时间复杂度分析(第1种输入形式)第1个for:n第2个for:n.e所以O(n.e)创建图创建图存储结构的转换存储结构的转换void TranslateDG(ALGraph G1,MGraph G2)/设置参数 G2.GraghKind

23、=G1.GraghKind;G2.vexNum=G1.vexNum;G2.arcNum=G1.arcNum /复制顶点 for(i=0;iG1.vexNum;i+)G2.vexsi=G1.verticesi.data;/复制弧 for(i=0;iG2.vexNum;i+)for(j=0;jG2.vexNum;j+)G2.arcsij=0;for(i=0;iG1.vexNum;i+)/复制G1每个顶点的邻接点p=G1.verticesi.firstarc;while(p)G2.arcsip.adjvex=1;p=p.nextarc;存储结构的转换存储结构的转换void TranslateDG(ALGraph G1,MGraph G2)小结小结1.图的基本概念以及图的特点图的基本概念以及图的特点2.图的存储表示：图的存储表示：(1)图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示(2)图的邻接表存储表示图的邻接表存储表示 3.用用java语言描述图的存储结构语言描述图的存储结构(3)图的存储结构的比较图的存储结构的比较(1)firstAdjVex和和nextAdjVex(2)创建图创建图