拓?fù)渑判驅(qū)嶒?yàn)報(bào)告_第1頁(yè)
拓?fù)渑判驅(qū)嶒?yàn)報(bào)告_第2頁(yè)
拓?fù)渑判驅(qū)嶒?yàn)報(bào)告_第3頁(yè)
拓?fù)渑判驅(qū)嶒?yàn)報(bào)告_第4頁(yè)
拓?fù)渑判驅(qū)嶒?yàn)報(bào)告_第5頁(yè)
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、實(shí)驗(yàn)題目: 圖的應(yīng)用 實(shí)驗(yàn)?zāi)康模?(1)熟練掌握?qǐng)D的基本存儲(chǔ)方法; (2)熟練掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先搜索方法; (3)掌握 AOV 網(wǎng)和拓?fù)渑判蛩惴ǎ?(4)掌握 AOE 網(wǎng)和關(guān)鍵路徑。 實(shí)驗(yàn)內(nèi)容: 拓?fù)渑判颉?任意給定一個(gè)有向圖,設(shè)計(jì)一個(gè)算法,對(duì)它進(jìn)行拓?fù)渑判?。拓?fù)渑判蛩惴ㄋ枷耄篴.在 有向圖中任選一個(gè)沒(méi)有前趨的頂點(diǎn)輸出;b.從圖中刪除該頂點(diǎn)和所有以它為尾的??; c.重復(fù)上述 a、b,直到全部頂點(diǎn)都已輸出,此時(shí),頂點(diǎn)輸出序列即為一個(gè)拓樸有序 序列;或者直到圖中沒(méi)有無(wú)前趨的頂點(diǎn)為止,此情形表明有向圖中存在環(huán)。 設(shè)計(jì)分析: 為實(shí)現(xiàn)對(duì)無(wú)權(quán)值有向圖進(jìn)行拓?fù)渑判?,輸出拓?fù)湫蛄?,先考慮如何存儲(chǔ)這個(gè)有

2、向圖。 拓?fù)渑判虻倪^(guò)程中要求找到入度為 0 的頂點(diǎn),所以要采用鄰接表來(lái)存儲(chǔ)有向圖,而要得到 鄰接表,則先要定義有向圖的鄰接矩陣結(jié)構(gòu),再把鄰接矩陣轉(zhuǎn)化成鄰接表。 在具體實(shí)現(xiàn)拓?fù)渑判虻暮瘮?shù)中,根據(jù)規(guī)則,當(dāng)某個(gè)頂點(diǎn)的入度為 0(沒(méi)有前驅(qū)頂點(diǎn)) 時(shí),就將此頂點(diǎn)輸出,同時(shí)將該頂點(diǎn)的所有后繼頂點(diǎn)的入度減 1,為了避免重復(fù)檢測(cè)入度 為 0 的頂點(diǎn),設(shè)立一個(gè)棧 St,以存放入度為 0 的頂點(diǎn)。 源程序代碼: #include #include #define MAXV 10 / 最大頂點(diǎn)個(gè)數(shù) typedef struct int edgesMAXVMAXV; / 鄰接矩陣的邊數(shù)組 int n; / 頂點(diǎn)數(shù) M

3、Graph; typedef struct ANode int adjvex; / 該弧的終點(diǎn)位置 struct ANode * nextarc; / 指向下一條弧的指針 ArcNode; typedef struct int no; / 頂點(diǎn)信息 int count; / 頂點(diǎn)入度 ArcNode * firstarc; / 指向第一條弧 VNode, AdjListMAXV; typedef struct AdjList adjlist; / 鄰接表 int n; / 圖的頂點(diǎn)數(shù) ALGraph; void MatTolist(MGraph g, ALGraph * ArcNode * p

4、; G = (ALGraph *)malloc(sizeof(ALGraph); for (i=0; iadjlisti.firstarc = NULL; for (i=0; i=0; j-) if (g.edgesij!=0) p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex = j; p-nextarc = G-adjlisti.firstarc; G-adjlisti.firstarc = p; G-n=n; void TopSort(ALGraph * G) int i,j,flag=0,aMAXV; int StMAXV, top = -1;

5、 / 棧 St 的指針為 top ArcNode * p; for (i=0; in; i+) / 入度置初值為 0 G-adjlisti.count = 0; for (i=0; in; i+) / 求所有頂點(diǎn)的入度 p=G-adjlisti.firstarc; while (p!=NULL) G-adjlistp-adjvex.count+; p=p-nextarc; for (i=0; in; i+) if (G-adjlisti.count=0) / 入度為 0 的頂點(diǎn)進(jìn)棧 top+; Sttop = i; while (top-1) / 棧不為空時(shí)循環(huán) i = Sttop; top-

6、; / 出棧 aflag+=i; / 輸出頂點(diǎn) p=G-adjlisti.firstarc; / 找第一個(gè)相鄰頂點(diǎn) while (p!=NULL) j = p-adjvex; G-adjlistj.count-; if (G-adjlistj.count=0) top+; Sttop = j; / 入度為 0 的相鄰頂點(diǎn)進(jìn)棧 p = p-nextarc; / 找下一個(gè)相鄰頂點(diǎn) if (flagn) printf(該圖存在回路,不存在拓?fù)湫蛄?n); else printf(該圖的一個(gè)拓?fù)湫蛄袨?); for(i=0; iflag; i+) printf(%d, ai); printf(n);

7、void main() int i, j; MGraph g; ALGraph * G; G=(ALGraph *)malloc(sizeof(ALGraph); printf(請(qǐng)輸入圖的頂點(diǎn)數(shù):); scanf(%d, printf(請(qǐng)輸入圖的鄰接矩陣:n); for(i=0; ig.n; i+) for(j=0; jg.n; j+) scanf(%d, MatTolist(g, G); TopSort(G); 測(cè)試用例: 對(duì)圖 7-1 所示的有向圖進(jìn)行拓?fù)渑判虻臏y(cè)試結(jié)果如下: 01 4 2 5 3 圖 7-1 圖 7-2 程序執(zhí)行界面,提示輸入圖的頂點(diǎn)數(shù),輸入之后又提示輸入其鄰接矩陣,對(duì)圖 7-1 所 示的有向圖的鄰接矩陣輸入如圖 7-2 所示。 圖 7-3 由于進(jìn)棧出戰(zhàn)的頂點(diǎn)順序已由程序代碼本身決定了,所以最終結(jié)果只能輸出該有向圖 的一個(gè)拓?fù)湫蛄?,如圖 7-3 所示。 對(duì)圖 7-4 所示的有向圖進(jìn)行拓?fù)渑判?,由于圖中存在回路,則無(wú)法得到拓?fù)湫蛄?,如圖 7-5 所示。 01 23 圖 7-4 圖 7-5 實(shí)驗(yàn)總結(jié): 本次試驗(yàn)通過(guò)對(duì)有向圖進(jìn)行拓?fù)渑判颍伊私饬擞邢驁D的鄰接矩陣和鄰接表的存儲(chǔ)結(jié) 構(gòu)以

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論