數(shù)據(jù)結(jié)構(gòu)第7章答案

答:11、設(shè)圖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、圖的存儲結(jié)構(gòu)定義如下：typedefstructArcCell{VRTypeadj;/*圖中有1/0表示是否有邊，網(wǎng)中表示邊上的權(quán)值*//*InfoType*info;與邊相關(guān)的信息*/}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*頂點向量*/AdjMatrixarcs;/*鄰接矩陣*/intvexnum,arcnum;/*圖中當(dāng)前頂點數(shù)和邊數(shù)*/}MGraph;請寫出下面函數(shù)實現(xiàn)的功能：頂點在頂點向量中的定位。intLocateVex(MGraphG,VertexTypev){inti;for(i=0;i〈G.vexnum;i++)if(strcmp(v,G.vexs[i])==0)break;returni;}下面函數(shù)的功能是在圖中查找第1個鄰接點，請?zhí)羁?。intFirstAdjVex(MGraphG,intv){intj,p=-1;for(j=0;j〈G.vexnum;j++)if(G.arcs[v][j].adj==1){p=j;break;}returnp;下面函數(shù)的功能是在圖中查找下一個鄰接點，請?zhí)羁?。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;//邊表結(jié)點結(jié)構(gòu)描述typedefstruct{charvertex;//頂點域EdgeNode*firstedge;//邊表頭指針}VertexNode;//頂點表結(jié)點結(jié)構(gòu)描述typedefstruct{VertexNodeadjlist[MaxNum];//鄰接表intn,e;}AlGraph;//鄰接表結(jié)構(gòu)描述下列算法輸出圖G的深度優(yōu)先生成樹(或森林)的邊，閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為個完整的算法。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;}}六、算法設(shè)計題01、編寫編歷算法，完成對圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。答：深度優(yōu)先搜索：課本P169算法7.4和算法7.5廣度優(yōu)先搜索：課本P170算法7.602、編寫算法，由依次輸入的頂點數(shù)目、弧的數(shù)目、各頂點的信息和各條弧的信息建立有向圖的鄰接表。答：StatusBuild_AdjList(ALGraph&G)//輸入有向圖的頂點數(shù)，邊數(shù)，頂點信息和邊的信息建立鄰接表{InitALGraph(G);scanf("%d"，&v);if(v〈0)returnERROR;//頂點數(shù)不能為負G.vexnum=v;scanf("%d"，&a);

if(a<0)returnERROR;//邊數(shù)不能為負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、試在鄰接矩陣存儲結(jié)構(gòu)上實現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。提示：要刪除所有從第i個頂點出發(fā)的邊，即將鄰接矩陣的第i行全部置0。答：//本題中的圖G均為有向無權(quán)圖。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;設(shè)計算法分別實現(xiàn)以下要求求出圖G中每個頂點的出度；求出圖G中出度最大的一個頂點,計算圖G中出度為0的頂點數(shù)；//鄰接點域//鏈指針域//邊表結(jié)點結(jié)構(gòu)描述//頂點域//邊表頭指針//頂點向量結(jié)點結(jié)構(gòu)描述//鄰接表//鄰接表結(jié)構(gòu)描述輸出該頂點號及其信息判斷圖G中是否存在弧〈i,j〉。答：本題答案見實驗部分05、試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點v到頂點v的ij路徑(i^j)。注意：算法中涉及的圖的基本操作必須在此存儲結(jié)構(gòu)上實現(xiàn)。答：intvisited[MAXSIZE];//指示頂點是否在當(dāng)前路徑上intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖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(luò)有路徑}//for}//else}//exist_path_DFS解2：(以上算法似乎有問題：如果不存在路徑，則原程序不能返回0。我的解決方式是在原程序的中引入一變量level來控制遞歸進行的層數(shù)。具體的方法我在程序中用紅色標(biāo)記出來了。)intvisited[MAXSIZE];//指示頂點是否在當(dāng)前路徑上intlevel=l;//遞歸進行的層數(shù)intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點i到頂點j是否有路徑,是則返回1,否則返回0{if(i==j)return1;//i就是jelse{vis