《数据结构》9.1图的基本概念和存储结构.ppt

图和图的存储结构1.图的定义图的定义图的定义—有向图图的定义—无向图图的定义—无向图名词和术语1）子图、网弧或边带权的图分别称作有向网或无向网。2）完全图、稀疏图、稠密图3）邻接点、度、入度、出度3）邻接点、度、入度、出度3）邻接点、度、入度、出度3）邻接点、度、入度、出度A简单路径:指序列中顶点不重复出现的路径。5）连通图、强连通图、弱连通图名词和术语强连通图：若有向图任意两个顶点之间都存在一条有向路径，则称为强连通图。基本操作CreatGraph(V,E)://按定义(V,E)构造图2.对顶点的访问操作3.插入或删除顶点4.插入和删除弧5.对邻接点的操作6.遍历一、图的数组(邻接矩阵)存储表示图的存储表示--邻接矩阵图的存储表示--邻接矩阵图的存储表示--邻接矩阵网的存储表示--邻接矩阵图的存储表示--邻接矩阵图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表存储结构的比较存储结构的比较存储结构的比较存储结构的比较存储结构的比较存储结构的比较存储结构的比较课堂练习V2下面关于图的存储的叙述中正确的是（）A）用相邻矩阵法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关C）用邻接表法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关用java语言描述存储结构邻接点函数的实现邻接点函数的实现邻接点函数的实现创建图1、图的两个个参数：1、输入参数:vexNum,arcNumvoidcreateDG(){//输入顶点数vexNum，边的条数arcNumfor(inti=0;i<vexNum;i++){//输入顶点信息,data为输入的顶点数据vertexs[i].data=sc.next;}for(intj=0;j<arcNum;j++){//输入边的信息,<v,w>为输入的弧信息intv=sc.nextInt,w=sc.nextInt;Arcp=newArc(w);//建立节点p.adjVex=w;p.nextArc=vertices[v].firstarc;//顶点v的链表vertices[v].firstArc=p;//添加到最左边}}voidcreateUDG(){//输入顶点数vexNum，边的条数arcNumfor(inti=0;i<vexNum;i++){//输入顶点信息,data为输入的顶点数据vertexs[i].data=sc.next;}for(intj=0;j<arcNum;j++){//输入边的信息,<v,w>为输入的弧信息intv=sc.nextInt,w=sc.nextInt;Arcp=newArc(w);p.nextArc=vertexs[v].firstArc;vertexs[v].firstArc=p;Arcq=newArc(v);q.nextArc=vertexs[w].firstArc;vertexs[w].firstArc=q;}}时间复杂度分析(第2种输入形式)第1个for:n第2个for:e所以O(n+e)存储结构的转换……for(i=0;i<G1.vexNum;i++){//复制G1每个顶点的邻接点p=G1.vertexs[i].firstarc;while(p){G2.arcs[i][p.adjvex]=1;p=p.nextarc;}}小结