1 / 28
文档名称:

数据结构第六次作业.doc

格式:doc   大小:458KB   页数:28页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构第六次作业.doc

上传人:glfsnxh 2020/8/7 文件大小:458 KB

下载得到文件列表

数据结构第六次作业.doc

文档介绍

文档介绍:第六次作业一、选择题1、在一个无向图中,所有顶点的度数之和等于所有边数的C倍。(握手定理) 、在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的B倍。 、G是一个非连通无向图,共有28条边,则该图至少有D个顶点。 //首先连通图顶点一定边数最多的情况为各顶点倆俩相连,此时边数为n(n-1)/2,则当顶点个数为8的时候边数最多为28,又G是非连通图,至少有一个独立的点,所以该图至少有9个顶点。4、有n个顶点的图的邻接矩阵使用B数组存储的。 、对于一个具有n个顶点和e条边的无向图,采用邻接表表示,则表头数组大小至少为(假设下标为0的数组参与使用)C。 -1 +1 +e6、下列说法正确的是C。 、填空题1、若无向图G中顶点数为n,则图G至多有n*(n-1)/2条边;若G为有向图,则图G至多有n*(n-1)条边。2、图的存储结构主要有两种,分别是邻接矩阵和邻接表。3、若G是有向图,则把邻接到顶点v的顶点数目或边数目称为顶点v的入度;把邻接于顶点v的顶点数目或边数目称为顶点v的出度。4、已知一个图的邻接矩阵表示,计算第j个顶点的入度的方法是将第j列的1的个数相加,计算第j个顶点的出度的方法是将第j行的1的个数相加。5、若将图中的每条边都赋予一个权,则称这种带权的图为网络。6、无论是有向图还是无向图,顶点数n、边数e和各顶点的度D(vi)之间的关系为:(∑1-n)D(vi)=2e即n个顶点的总度数等于边数的两倍,握手定理。若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的简单路径为环或回路。如果图中任意一对顶点都是连通的,则称此图是连通图;非连通图的极大连通子图叫做连通分量。创建一个邻接矩阵图的复杂度是O(n*n);创建一个链接表图的复杂度是O(n+e)e为边数。三、已知一个无向图如下图所示,试给出该图的邻接矩阵和邻接表存储示意图(分别用矩阵和数组链表图表示),并编程分别实现该图的邻接矩阵表示和邻接表表示,要求编写两种表示方法的存储结构、相关基本操作,并在主函数中创建该图。//邻接矩阵表示:#include<iostream>usingnamespacestd;#defineNumVertices6typedefcharVertexData;//顶点类型typedefintEdgeData;//边上权值类型typedefstruct{VertexDatavexlist[NumVertices];EdgeDataedge[NumVertices][NumVertices];//邻接矩阵intn;//定点数inte;//边数}MTGraph;voidIniMGraph(MTGraph*G)//初始化邻接表{ for(inti=0;i<NumVertices;i++) for(intj=0;j<NumVertices;j++) G->edge[i][j]=0; G->n=0; G->e=0;}voidNewNode(MTGraph*G,VertexDatav)//添加顶点{ G->vexlist[G->n]=v; G->n++; }voidDelNode(MTGraph*G,intm)//删除顶点{ inti,j; if(G->n==0||m>=NumVertices)//没有顶点||不存在顶点m return; for(i=m;i<G->n-1;i++)//顶点m后面的顶点前移 G->vexlist[i]=G->vexlist[i+1]; //删除与第m个顶点相连的边 //删掉边数 for(i=0;i<G->n;i++) { if(G->edge[i][m]!=0) G->e--; } //邻接矩阵降阶 for(i=m;i<G->n-1;i++) for(j=0;j<G->n;j++) G->edge[i][j]=G->edge[i+1][j]; for(i=m;i<G->n-1;i++) for(j=0;j<G->n-1;j++) G->edge[j][i]=G->edge[j][i+1];//减掉顶点数 G->n--;}//判断v1和v2之间有没有边boolIsEdge(MTGraph*G,intv1,intv2){ if(v1>=0&&v1<G->n&&v2>=0&&v2<G->n&&v1!=v2) if(G->edge[v1][v2]!=0) returntrue; else returnfalse; ret