拓?fù)渑判驅(qū)嶒?yàn)報(bào)告

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)以