




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、實驗題目: 圖的應(yīng)用 實驗?zāi)康模?(1)熟練掌握圖的基本存儲方法; (2)熟練掌握圖的深度優(yōu)先和廣度優(yōu)先搜索方法; (3)掌握 AOV 網(wǎng)和拓?fù)渑判蛩惴ǎ?(4)掌握 AOE 網(wǎng)和關(guān)鍵路徑。 實驗內(nèi)容: 拓?fù)渑判颉?任意給定一個有向圖,設(shè)計一個算法,對它進行拓?fù)渑判颉M負(fù)渑判蛩惴ㄋ枷耄篴.在 有向圖中任選一個沒有前趨的頂點輸出;b.從圖中刪除該頂點和所有以它為尾的??; c.重復(fù)上述 a、b,直到全部頂點都已輸出,此時,頂點輸出序列即為一個拓樸有序 序列;或者直到圖中沒有無前趨的頂點為止,此情形表明有向圖中存在環(huán)。 設(shè)計分析: 為實現(xiàn)對無權(quán)值有向圖進行拓?fù)渑判?,輸出拓?fù)湫蛄?,先考慮如何存儲這個有
2、向圖。 拓?fù)渑判虻倪^程中要求找到入度為 0 的頂點,所以要采用鄰接表來存儲有向圖,而要得到 鄰接表,則先要定義有向圖的鄰接矩陣結(jié)構(gòu),再把鄰接矩陣轉(zhuǎn)化成鄰接表。 在具體實現(xiàn)拓?fù)渑判虻暮瘮?shù)中,根據(jù)規(guī)則,當(dāng)某個頂點的入度為 0(沒有前驅(qū)頂點) 時,就將此頂點輸出,同時將該頂點的所有后繼頂點的入度減 1,為了避免重復(fù)檢測入度 為 0 的頂點,設(shè)立一個棧 St,以存放入度為 0 的頂點。 源程序代碼: #include #include #define MAXV 10 / 最大頂點個數(shù) typedef struct int edgesMAXVMAXV; / 鄰接矩陣的邊數(shù)組 int n; / 頂點數(shù) M
3、Graph; typedef struct ANode int adjvex; / 該弧的終點位置 struct ANode * nextarc; / 指向下一條弧的指針 ArcNode; typedef struct int no; / 頂點信息 int count; / 頂點入度 ArcNode * firstarc; / 指向第一條弧 VNode, AdjListMAXV; typedef struct AdjList adjlist; / 鄰接表 int 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+) / 求所有頂點的入度 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 的頂點進棧 top+; Sttop = i; while (top-1) / 棧不為空時循環(huán) i = Sttop; top-
6、; / 出棧 aflag+=i; / 輸出頂點 p=G-adjlisti.firstarc; / 找第一個相鄰頂點 while (p!=NULL) j = p-adjvex; G-adjlistj.count-; if (G-adjlistj.count=0) top+; Sttop = j; / 入度為 0 的相鄰頂點進棧 p = p-nextarc; / 找下一個相鄰頂點 if (flagn) printf(該圖存在回路,不存在拓?fù)湫蛄?n); else printf(該圖的一個拓?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(請輸入圖的頂點數(shù):); scanf(%d, printf(請輸入圖的鄰接矩陣:n); for(i=0; ig.n; i+) for(j=0; jg.n; j+) scanf(%d, MatTolist(g, G); TopSort(G); 測試用例: 對圖 7-1 所示的有向圖進行拓?fù)渑判虻臏y試結(jié)果如下: 01 4 2 5 3 圖 7-1 圖 7-2 程序執(zhí)行界面,提示輸入圖的頂點數(shù),輸入之后又提示輸入其鄰接矩陣,對圖 7-1 所 示的有向圖的鄰接矩陣輸入如圖 7-2 所示。 圖 7-3 由于進棧出戰(zhàn)的頂點順序已由程序代碼本身決定了,所以最終結(jié)果只能輸出該有向圖 的一個拓?fù)湫蛄校鐖D 7-3 所示。 對圖 7-4 所示的有向圖進行拓?fù)渑判颍捎趫D中存在回路,則無法得到拓?fù)湫蛄校鐖D 7-5 所示。 01 23 圖 7-4 圖 7-5 實驗總結(jié): 本次試驗通過對有向圖進行拓?fù)渑判?,我了解了有向圖的鄰接矩陣和鄰接表的存儲結(jié) 構(gòu)以
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 管理崗位績效管理辦法
- 學(xué)校地基歸誰管理辦法
- 競賽教練考核管理辦法
- 腸息肉中醫(yī)教學(xué)課件
- 福建第三次質(zhì)檢數(shù)學(xué)試卷
- 汾陽初中二模數(shù)學(xué)試卷
- 畢業(yè)設(shè)計(論文)-家用照明智能控制系統(tǒng)的設(shè)計
- 2025至2030大米行業(yè)市場深度研究與戰(zhàn)略咨詢分析報告
- 德國職業(yè)教育的數(shù)字化轉(zhuǎn)型:戰(zhàn)略規(guī)劃、項目布局與效果評估
- 麗水農(nóng)林技師學(xué)院招聘教師筆試真題2024
- 2025年綏化市中考化學(xué)試題卷(含答案解析)
- 危重病人觀察和護理要點
- GB/T 45719-2025半導(dǎo)體器件金屬氧化物半導(dǎo)體(MOS)晶體管的熱載流子試驗
- 寶媽日常心理護理
- 2025年社會學(xué)概論測試題含答案(附解析)
- 2025-2030年環(huán)境工程產(chǎn)業(yè)深度調(diào)研及發(fā)展趨勢與投資戰(zhàn)略研究報告
- 2025年事業(yè)單位公開招聘考試(E類)《綜合應(yīng)用能力西醫(yī)臨床》試卷真題及完整解析
- 保險公司保單管理制度
- 2025年中國AI翻譯行業(yè)市場全景分析及前景機遇研判報告
- 2025-2030中國酶聯(lián)免疫吸附測定(ELISA)行業(yè)市場發(fā)展趨勢與前景展望戰(zhàn)略研究報告
- 2025年內(nèi)蒙古眾達人力資源公司招聘題庫帶答案分析
評論
0/150
提交評論