南工大第四章-图

数据结构与算法上机作业第四章图

一、选择题1、在一个无向图中，所有顶点的度数之和等于所有边数的C倍。 A.1/2 B.1 C.2 D.42、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的B倍。 A.1/2 B.1 C.2 D.43、G是一个非连通无向图，共有28条边，则该图至少有D个顶点。 A.6 B.7 C.8 D.94、有n个顶点的图的邻接矩阵使用B数组存储的。 A.一维 B.n行n列 C.任意行n列 D.n行任意列5、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头数组大小至少为（假设下标为0的数组参与使用）A。 A.n-1 B.n+1 C.n D.n+e6、下列说法正确的是C。 A.有向图的邻接矩阵一定是不对称的 B.有向图的邻接矩阵一定是对称的 C.无向图的邻接矩阵一定是对称的 D.无向图的邻接矩阵可以不对称7、深度优先遍历类似与二叉树的A：A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历8、广度优先遍历类似与二叉树的D：A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历9、下列关于开放树(FreeTree)的说法错误的是C：A.具有n个结点的开放树包含n-1条边B.开放树没有回路C.开放树可以是非连通图D.在开放树中任意加一条边，一定会产生回路10、在如下图所示的图中，从顶点a出发，按深度优先遍历，则可能得到的一种顶点的序列为。A.a,b,e,c,d,f B.a,c,f,e,b,dC.a,e,b,c,f,d D.a,e,d,f,c,b11、在如上图所示的图中，从顶点a出发，按广度优先遍历，则可能得到的一种顶点的序列为。 A.a,b,e,c,d,f B.a,b,e,c,f,d C.a,e,b,c,f,d D.a,e,d,f,c,b12、设网(带权的图)有n个顶点和e条边，则采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为C。 returnv;}//寻找某个顶点的位置intFindPosition(Graph*G,charv){ for(inti=0;i<G->count;i++){ if(v==G->vexs[i]) returni; }}voidDelete(Graph*G,charv){ //先删除点 inti,j; inttemp_count=G->count;i=FindPosition(G,v); for(j=i;j<temp_count;j++) G->vexs[j]=G->vexs[j+1]; G->count--; //删除边 //先删除行 intp=i;//记住位置 for(i=p;i<temp_count-1;i++) for(j=0;j<temp_count;j++) G->arcs[i][j]=G->arcs[i+1][j]; //再删除列 for(i=p;i<temp_count-1;i++) for(j=0;j<temp_count;j++) G->arcs[j][i]=G->arcs[j][i+1]; }//建立v1与v2的一条边voidSetSoucc(Graph*G,charv1,charv2){ //先找到对应的定的位置 inti,j; inttemp_count=G->count; i=FindPosition(G,v1); j=FindPosition(G,v2); if(i==temp_count||j==temp_count)//没有找到 return; //找到后，A[i][j]=0;vexs[j][i]=0; G->arcs[i][j]=1; G->arcs[j][i]=1;}voidDelSucc(Graph*G,charv1,charv2){ inti,j; inttemp_count=G->count; i=FindPosition(G,v1); j=FindPosition(G,v2); if(i==temp_count||j==temp_count)//没有找到 return; //找到后，A[i][j]=0;vexs[j][i]=0; G->arcs[i][j]=0; G->arcs[j][i]=0;}//判断v1y与v2是否连接boolisEdge(Graph*G,charv1,charv2){ inti,j; inttemp_count=G->count; i=FindPosition(G,v1); j=FindPosition(G,v2); if(i==temp_count||j==temp_count)//没有找到 return-1; if(G->arcs[i][j]==1) returntrue; returnfalse; }voidPrint(Graph*G){ inti,j; for(i=0;i<G->count;i++){ for(j=0;j<G->count;j++) cout<<G->arcs[i][j]<<""; cout<<endl; } cout<<endl;}Graph*G=newGraph;//初始化intmain(){ G->count=0; NewNode(G,'A'); NewNode(G,'B');NewNode(G,'C'); NewNode(G,'D'); //插入边 SetSoucc(G,'A','B'); SetSoucc(G,'A','D'); SetSoucc(G,'C','B'); Print(G); //删除一个顶点 Delete(G,'C'); Print(G); //删除边 DelSucc(G,'A','D'); Print(G); if(isEdge(G,'A','B')) cout<<"A与B右边"<<endl; return0;}四、已知一个有向图如下图所示，试给出图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。代码：#include<iostream>#include<stdio.h>#include<stdlib.h>usingnamespacestd;#definemax_n20structArcNode{ charadjvex='#'; ArcNode*next=NULL;};typedefstructVNode{ chardata; ArcNode*first_head; }VNode,AdjList[max_n];typedefstruct{ AdjListvertices; intvexnum,arcnum; intcount=0;}Graph;//新增一个顶点charNewNode(Graph*G,charv){ G->vertices[G->count].data=v; G->vertices[G->count].first_head=newArcNode; G->count++; returnv;}//寻找某个顶点的位置intFindPosition(Graph*G,charv){ for(inti=0;i<G->count;i++){ if(v==G->vertices[i].data) returni; }}//删除一个顶点voidDelNode(Graph*G,charv){ inti=FindPosition(G,v); //去头 ArcNode*p=G->vertices[i].first_head; //现在vertices中删除 intj; for(j=i;j<G->count-1;j++) G->vertices[j]=G->vertices[j+1]; G->vertices[j].data='#'; G->vertices[j].first_head=NULL; G->count--; //删除边 ArcNode*q; while(p!=NULL){ q=p; p=p->next; q=NULL; }}//设置v1到v2直接的一条边voidSetSucc(Graph*G,charv1,charv2){ inti=FindPosition(G,v1); ArcNode*p; p=G->vertices[i].first_head; while(p->next!=NULL){ p=p->next; } ArcNode*q=newArcNode; q->adjvex=v2; p->next=q;}ArcNode*FindNode(ArcNode*p,charv2){for(;p;p=p->next){if(p->next->adjvex==v2)break;}returnp;}voidDetele(Graph*G,charv1,charv2){ inti=FindPosition(G,v1); ArcNode*p; //没有找到 if(i==-1) return; p=FindNode(G->vertices[i].first_head,v2); //因为p是上一个节点的位置，用q来保存//要删除的节点的地址ArcNode*q=p->next;//通过将上一个节点的next指针指向要删除节点的next指//针志向的节点实现断开要删除节点的目的//p->adjvex=p->next->adjvex;p->next=p->next->next;//删除要删除的节点qdeleteq; }//输出领接表voidPrint(Graph*G){ ArcNode*p; for(inti=0;i<G->count;i++){ //先将data cout<< G->vertices[i].data<<"->"; //从每个顶点的头结点开始遍历 if(G->vertices[i].first_head->next!=NULL){ p=G->vertices[i].first_head->next; while(p!=NULL){ cout<<p->adjvex<<"->"; p=p->next; } } cout<<endl; }cout<<endl;}Graph*G=newGraph;intmain(){ NewNode(G,'A'); NewNode(G,'B'); NewNode(G,'C'); NewNode(G,'D');Print(G);SetSucc(G,'A','D');SetSucc(G,'A','B');SetSucc(G,'A','C');SetSucc(G,'B','C');SetSucc(G,'C','D');SetSucc(G,'D','B');Print(G);Detele(G,'A','C');Detele(G,'D','B');Print(G);SetSucc(G,'D','C');Print(G); return0;}五、已知一个图的顶点集为{a,b,c,d,e}，其邻接矩阵如下图，考虑图为无向图和有向图两种情况，分别画出该图。六、已知一个连通图如下图所示，分别给出一个按深度优先遍历和广度优先遍历的顶点序列（假设从顶点v1出发）。并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写相关基本操作，并在主函数中求出深度优先序列和广度优先序列。代码：#include<iostream>#include<stdio.h>#include<stdlib.h>#include<queue>usingnamespacestd;#definemax_n20structArcNode{ charadjvex='#'; ArcNode*next=NULL;};typedefstructVNode{ chardata; ArcNode*first_head;}VNode,AdjList[max_n];typedefstruct{ AdjListvertices; intvisit[max_n]={0};//记录是否被访问过 intvexnum,arcnum; intcount=0;}Graph;//新增一个顶点charNewNode(Graph*G,charv){ G->vertices[G->count].data=v; G->vertices[G->count].first_head=newArcNode; G->count++; returnv;}//寻找某个顶点的位置intFindPosition(Graph*G,charv){ for(inti=0;i<G->count;i++){ if(v==G->vertices[i].data) returni; }}//删除一个顶点voidDelNode(Graph*G,charv){ inti=FindPosition(G,v); //去头 ArcNode*p=G->vertices[i].first_head; //现在vertices中删除 intj; for(j=i;j<G->count-1;j++) G->vertices[j]=G->vertices[j+1]; G->vertices[j].data='#'; G->vertices[j].first_head=NULL; G->count--; //删除边 ArcNode*q; while(p!=NULL){ q=p; p=p->next; q=NULL; }}//设置v1到v2直接的一条边voidSetSucc(Graph*G,charv1,charv2){ inti=FindPosition(G,v1); ArcNode*p; p=G->vertices[i].first_head; while(p->next!=NULL){ p=p->next; } ArcNode*q=newArcNode; q->adjvex=v2; p->next=q;}//对于无向图voidSetSucc1(Graph*G,charv1,charv2){ SetSucc(G,v1,v2); SetSucc(G,v2,v1);}ArcNode*FindNode(ArcNode*p,charv2){ for(;p;p=p->next){ if(p->next->adjvex==v2) break; } returnp;}voidDetele(Graph*G,charv1,charv2){ inti=FindPosition(G,v1); ArcNode*p; //没有找到 if(i==-1) return; p=FindNode(G->vertices[i].first_head,v2); //因为p是上一个节点的位置，用q来保存 //要删除的节点的地址 ArcNode*q=p->next; //通过将上一个节点的next指针指向要删除节点的next指 //针志向的节点实现断开要删除节点的目的//p->adjvex=p->next->adjvex; p->next=p->next->next; //删除要删除的节点q deleteq;}//输出领接表voidPrint(Graph*G){ ArcNode*p; for(inti=0;i<G->count;i++){ //先将data cout<< G->vertices[i].data<<"->"; //从每个顶点的头结点开始遍历 if(G->vertices[i].first_head->next!=NULL){ p=G->vertices[i].first_head->next; while(p!=NULL){ cout<<p->adjvex<<"->"; p=p->next; } } cout<<endl; } cout<<endl;}voidmakeVisitNull(Graph*G){ for(inti=0;i<max_n;i++) G->visit[i]=0;}voidDfs_part(Graph*G,inti){ ArcNode*p=G->vertices[i].first_head->next; for(;p;p=p->next){ inti=FindPosition(G,p->adjvex); if(!G->visit[i]){ G->visit[i]=1; cout<<p->adjvex<<"->"; Dfs_part(G,i); } }}//深度优先遍历voidDFS(Graph*G,inti){ cout<<G->vertices[i].data<<"->"; G->visit[i]=1; Dfs_part(G,i); //恢复 makeVisitNull(G);cout<<endl;}queue<int>qList;voidBfs_part(Graph*G){intt= qList.front(); cout<<G->vertices[t].data<<"->"; qList.pop(); ArcNode*p=G->vertices[t].first_head->next; for(;p;p=p->next){ inti=FindPosition(G,p->adjvex); if(!G->visit[i]){ G->visit[i]=1; qList.push(i); } } if(!qList.empty()) Bfs_part(G);}//voidBFS(Graph*G,inti){ G->visit[i]=1; qList.push(i); Bfs_part(G); //恢复 makeVisitNull(G); cout<<endl;}Graph*G=newGraph;intmain(){ NewNode(G,'1'); NewNode(G,'2'); NewNode(G,'3'); NewNode(G,'4'); NewNode(G,'5'); NewNode(G,'6'); Print(G); SetSucc1(G,'1','2'); SetSucc1(G,'1','4'); SetSucc1(G,'1','6'); SetSucc1(G,'2','3'); SetSucc1(G,'2','4'); SetSucc1(G,'2','5'); SetSucc1(G,'3','5'); SetSucc1(G,'4','6'); SetSucc1(G,'4','5'); Print(G);cout<<"DFS:"<<endl;DFS(G,0);cout<<"BFS:"<<endl;BFS(G,0); return0;}七、基于深度优先搜索算法，写出求无向图所有连通子图的算法，并求连通分量。提示：对于无向图，从任一个顶点出发进行DFS遍历，当本次遍历完成后，其所访问的结点构成一个连通子图；如果还存在没有访问过的结点，则从中任一个结点出发进行DFS遍历，……，直到所有结点都被访问。每一次调用DFS后都得到此非连通图的一个连通子图，调用DFS的次数就是连通子图的个数。八、网络G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。解：下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim算法和Kruskal算法求最小生成树（包括算法代码和画图）。代码：#include<iostream>#include<vector>#include<queue>#include<algorithm>usingnamespacestd;#defineINFINITE0xFFFFFFFF#defineVertexDataunsignedint//顶点数据#defineUINTunsignedint#definevexCounts6//顶点数量charvextex[]={'A','B','C','D','E','F'};structnode{ VertexDatadata; unsignedintlowestcost;}closedge[vexCounts];//Prim算法中的辅助信息typedefstruct{ VertexDatau; VertexDatav; unsignedintcost;//边的代价}Arc;//原始图的边信息voidAdjMatrix(unsignedintadjMat[][vexCounts]){//邻接矩阵表示法 for(inti=0;i<vexCounts;i++)//初始化邻接矩阵 for(intj=0;j<vexCounts;j++){ adjMat[i][j]=INFINITE; } }intMinmum(structnode*closedge){//返回最小代价边 unsignedintmin=INFINITE; intindex=-1; for(inti=0;i<vexCounts;i++){ if(closedge[i].lowestcost<min&&closedge[i].lowestcost!=0){ min=closedge[i].lowestcost; index=i; } } returnindex;}voidMiniSpanTree_Prim(unsignedintadjMat[][vexCounts],VertexDatas){ for(inti=0;i<vexCounts;i++){ closedge[i].lowestcost=INFINITE; } closedge[s].data=s;//从顶点s开始 closedge[s].lowestcost=0; for(inti=0;i<vexCounts;i++){//初始化辅助数组 if(i!=s){ closedge[i].data=s; closedge[i].lowestcost=adjMat[s][i]; } } for(inte=1;e<=vexCounts-1;e++){//n-1条边时退出 intk=Minmum(closedge);//选择最小代价边 cout<<vextex[closedge[k].data]<<"--"<<vextex[k]<<endl;//加入到最小生成树 closedge[k].lowestcost=0;//代价置为0 for(inti=0;i<vexCounts;i++){//更新v中顶点最小代价边信息 if(adjMat[k][i]<closedge[i].lowestcost){ closedge[i].data=k; closedge[i].lowestcost=adjMat[k][i]; } } }}voidReadArc(unsignedintadjMat[][vexCounts],vector<Arc>&vertexArc){//保存图的边代价信息 Arc*temp=NULL; for(unsignedinti=0;i<vexCounts;i++){ for(unsignedintj=0;j<i;j++){ if(adjMat[i][j]!=INFINITE){ temp=newArc; temp->u=i; temp->v=j; temp->cost=adjMat[i][j]; vertexArc.push_back(*temp); } } }}boolcompare(ArcA,ArcB){ returnA.cost<B.cost?true:false;}boolFindTree(VertexDatau,VertexDatav,vector<vector<VertexData>>&Tree){ unsignedintindex_u=INFINITE; unsignedintindex_v=INFINITE; for(unsignedinti=0;i<Tree.size();i++){//检查u,v分别属于哪颗树 if(find(Tree[i].begin(),Tree[i].end(),u)!=Tree[i].end()) index_u=i; if(find(Tree[i].begin(),Tree[i].end(),v)!=Tree[i].end()) index_v=i; } if(index_u!=index_v){//u,v不在一颗树上，合并两颗树 for(unsignedinti=0;i<Tree[index_v].size();i++){ Tree[index_u].push_back(Tree[index_v][i]); } Tree[index_v].clear(); returntrue; } returnfalse;}voidMiniSpanTree_Kruskal(unsignedintadjMat[][vexCounts]){ vector<Arc>vertexA