数据结构第7章答案

答:11、设图G=(V,E),V={1,2,3,4,5,6},E={〈1,2〉，〈1,3〉，〈2,5〉，〈3,6〉，〈6,5〉，〈5,4〉，〈6,4〉}。画出图G,并写出图G中顶点的所有拓扑序列。1,2,3,6,5,41,3,2,6,5,41,3,6,2,5,4五、代码填空题01、图的存储结构定义如下：typedefstructArcCell{VRTypeadj;/*图中有1/0表示是否有边，网中表示边上的权值*//*InfoType*info;与边相关的信息*/}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图中当前顶点数和边数*/}MGraph;请写出下面函数实现的功能：顶点在顶点向量中的定位。intLocateVex(MGraphG,VertexTypev){inti;for(i=0;i〈G.vexnum;i++)if(strcmp(v,G.vexs[i])==0)break;returni;}下面函数的功能是在图中查找第1个邻接点，请填空。intFirstAdjVex(MGraphG,intv){intj,p=-1;for(j=0;j〈G.vexnum;j++)if(G.arcs[v][j].adj==1){p=j;break;}returnp;下面函数的功能是在图中查找下一个邻接点，请填空。intNextAdjVex(MGraphG,intv,intw){intj,p=-1;for(j二w+1;j〈G.vexnum;j++)if(G.arcs[v][j].adj==l){p=j;break;}returnp;}02、已知图的邻接表表示的形式说明如下：#defineMaxNum80typedefstructnode{intadjvex;//邻接点域structnode*next;//链指针域}EdgeNode;//边表结点结构描述typedefstruct{charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;//顶点表结点结构描述typedefstruct{VertexNodeadjlist[MaxNum];//邻接表intn,e;}AlGraph;//邻接表结构描述下列算法输出图G的深度优先生成树(或森林)的边，阅读算法，并在空缺处填入合适的内容，使其成为个完整的算法。typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxNum];voidDFSForest(AlGraph*G){for(i=0;i〈G-〉n;i++)visited[i]二FALSE;for(i=0;i〈G-〉n;i++)if(!visited[i])DFSTree(G,i);}voidDFSTree(AlGraph*G,inti){visited[i]=TRUE;p=G-〉adjlist[i].firstedge;while(p!=NULL){if(!visited[p-〉adjves]){printf(G-〉adjlist[i].vertex,G-〉adjlist[p-〉adjvex].vertex);DSFTree(G,p-〉adjvex);}p=p-〉next;}}六、算法设计题01、编写编历算法，完成对图的深度优先搜索和广度优先搜索。答：深度优先搜索：课本P169算法7.4和算法7.5广度优先搜索：课本P170算法7.602、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。答：StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数，边数，顶点信息和边的信息建立邻接表{InitALGraph(G);scanf("%d"，&v);if(v〈0)returnERROR;//顶点数不能为负G.vexnum=v;scanf("%d"，&a);

if(a<0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data=getchar();//输入各顶点的符号for(m=1;m<=a;m++){t=getchar();h=getchar();//t为弧尾,h为弧头if((i=LocateVex(G,t))<0)returnERROR;if((j=LocateVex(G,h))<0)returnERROR;//顶点未找到p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;}p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//Build_AdjList03、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。提示：要删除所有从第i个顶点出发的边，即将邻接矩阵的第i行全部置0。答：//本题中的图G均为有向无权图。StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc04、有n个顶点的有向图的邻接表定义如下04、有n个顶点的有向图的邻接表定义如下:#defineMaxNum80typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstedge;}VNode,AdjList[MaxNum];typedefstruct{AdjListvertices;intvexnum,arcnum;}AlGraph;设计算法分别实现以下要求求出图G中每个顶点的出度；求出图G中出度最大的一个顶点,计算图G中出度为0的顶点数；//邻接点域//链指针域//边表结点结构描述//顶点域//边表头指针//顶点向量结点结构描述//邻接表//邻接表结构描述输出该顶点号及其信息判断图G中是否存在弧〈i,j〉。答：本题答案见实验部分05、试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点v到顶点v的ij路径(i^j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。答：intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p-〉nextarc){k=p-〉adjvex;辻(!visited[k]&&exist_path(k,j))returnl;//i下游的顶点到j有路径}//for}//else}//exist_path_DFS解2：(以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。)intvisited[MAXSIZE];//指示顶点是否在当前路径上intlevel=l;//递归进行的层数intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{vis