




下載本文檔
版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 海南桔子花期管理辦法
- ??诘叵驴臻g管理辦法
- 深圳失業(yè)登記管理辦法
- 培訓(xùn)實(shí)施課件模板下載
- 基于項(xiàng)目式學(xué)習(xí)的初中科學(xué)教育實(shí)踐研究
- 寫作格式培訓(xùn)課件圖片
- 交通運(yùn)輸衛(wèi)星導(dǎo)航增強(qiáng)服務(wù)性能指標(biāo)及監(jiān)測(cè)技術(shù)規(guī)范編制說(shuō)明
- 采茶廠黑名單客戶準(zhǔn)入限制制度
- 個(gè)性化健身成就獎(jiǎng)勵(lì)系統(tǒng)界面考核試卷
- 醫(yī)療旅游業(yè)AI輔助診斷系統(tǒng)企業(yè)制定與實(shí)施新質(zhì)生產(chǎn)力項(xiàng)目商業(yè)計(jì)劃書
- 設(shè)備移交協(xié)議書模板
- 2025三季度四川經(jīng)準(zhǔn)檢驗(yàn)檢測(cè)集團(tuán)股份限公司招聘48人易考易錯(cuò)模擬試題(共500題)試卷后附參考答案
- 網(wǎng)約車法律培訓(xùn)
- 深圳市羅湖區(qū)2025年小升初數(shù)學(xué)模擬試卷含解析
- 軸承加工合同協(xié)議
- 慢阻肺診療規(guī)范
- 2024-2025北師大版小學(xué)數(shù)學(xué)四年級(jí)上冊(cè)期末考試測(cè)試卷及參考答案(共三套)
- 黑龍江省普通高中2024年1月學(xué)業(yè)水平合格性考試 數(shù)學(xué)試題(真題)
- 《互聯(lián)網(wǎng)產(chǎn)品開(kāi)發(fā)》教學(xué)教案
- 職業(yè)院校教師人工智能素養(yǎng):內(nèi)涵流變、框架構(gòu)建與生成路徑
- 校園信息化建設(shè)中的技術(shù)難題與解決方案
評(píng)論
0/150
提交評(píng)論