第七章圖一、選擇題1．C,E；2．B,D；3．B,A；4．B；5．D；6．A,B；7．A,D；8．B；9．C,B；10．B；11．D；12．B；13．B；14．D；15．A。二、填空題1、2；2、1；3、6；4、5；5、；6、n，2e；7、先序（根），按層；8、深；9、m/2；10、O（n2），稠密圖；11、O（eloge），稀疏圖；12、O（n+m）；13、O（n2）；14、O（n3）；15、9；三、計(jì)算題1、（a）(c)(d)是連通圖，(b)是非連通圖，兩個(gè)連通分量是{1，4}，{2，3}2、(1)頂點(diǎn)度入度出度V1312V2211V3321V4211(2)3、4、5、12①②56③④⑤49⑥6、關(guān)鍵路徑：v1v2v3v5v6及v1v4v6；活動(dòng)V3的最早開始時(shí)間是13。7、152364；152634；156234；561234；512354；516234；512634；5123648、拓?fù)湫蛄袨?25143678。9、（1）DFS:１２３５４６BFS:１２４６３５（2）（3）四、算法設(shè)計(jì)題1、intAlinkB(GraphG,VertexTypeA,VertexTypeB){for(v=0;v<G.vernum;++v)visited[v]=FALSE;DFS(G,A);If(Visited[B])return1;Elsereturn0;}2、intnum(GraphG){n=0;for(v=0;v<G.vernum;++v)visited[v]=FALSE;for(v=0;v<G.vernum;++v)If(!Visited[V])DFS(G,v);n++;returnn;}3.voidShortPath(GraphG,intu,intv){//輸出從頂點(diǎn)u到頂點(diǎn)v的最短逆路徑EdgeNode*p;intw,i;QUEREqu[MAXV]; //定義非循環(huán)隊(duì)列intfront=-1,rear=-1; //隊(duì)列的頭、尾指針intvisited[MAXV];for(i=0;i<G->n;i++) //訪問標(biāo)記置初值0 visited[i]=0;rear++; //頂點(diǎn)u進(jìn)隊(duì)qu[rear].data=u;qu[rear].parent=-1;visited[u]=1;while(front!=rear) //隊(duì)不空循環(huán){front++; //出隊(duì)頂點(diǎn)ww=qu[front].data;if(w==v) {i=front; while(qu[i].parent!=-1) {printf("%2d",qu[i].data); i=qu[i].parent; } printf("%2d\n",qu[i].data); return;}p=G->adjlist[w].firstedge; //找w的第一個(gè)鄰接點(diǎn)while(p!=NULL){if(visited[p->adjvex]==0) {visited[p->adjvex]=1;rear++; //將w的未訪問過的鄰接點(diǎn)進(jìn)隊(duì)qu[rear].data