上傳人：g***

認證信息

認證類型：個人認證

認證主體：余**（實名認證）

IP屬地：貴州

IP屬地：貴州 上傳時間：2020-06-22 格式：DOC 頁數(shù)：5 大?。?2KB 積分：20 舉報 版權(quán)申訴

1、實驗題目： 圖的應(yīng)用 實驗?zāi)康模?（1）熟練掌握圖的基本存儲方法； （2）熟練掌握圖的深度優(yōu)先和廣度優(yōu)先搜索方法； （3）掌握 AOV 網(wǎng)和拓撲排序算法； （4）掌握 AOE 網(wǎng)和關(guān)鍵路徑。 實驗內(nèi)容： 拓撲排序。 任意給定一個有向圖，設(shè)計一個算法，對它進行拓撲排序。拓撲排序算法思想：a.在 有向圖中任選一個沒有前趨的頂點輸出；b.從圖中刪除該頂點和所有以它為尾的??； c.重復(fù)上述 a、b，直到全部頂點都已輸出，此時，頂點輸出序列即為一個拓樸有序 序列；或者直到圖中沒有無前趨的頂點為止，此情形表明有向圖中存在環(huán)。 設(shè)計分析： 為實現(xiàn)對無權(quán)值有向圖進行拓撲排序，輸出拓撲序列，先考慮如何存儲這個有

2、向圖。 拓撲排序的過程中要求找到入度為 0 的頂點，所以要采用鄰接表來存儲有向圖，而要得到 鄰接表，則先要定義有向圖的鄰接矩陣結(jié)構(gòu)，再把鄰接矩陣轉(zhuǎn)化成鄰接表。 在具體實現(xiàn)拓撲排序的函數(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(該圖存在回路，不存在拓撲序列!n); else printf(該圖的一個拓撲序列為:); 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 所示的有向圖進行拓撲排序的測試結(jié)果如下： 01 4 2 5 3 圖 7-1 圖 7-2 程序執(zhí)行界面，提示輸入圖的頂點數(shù)，輸入之后又提示輸入其鄰接矩陣，對圖 7-1 所 示的有向圖的鄰接矩陣輸入如圖 7-2 所示。 圖 7-3 由于進棧出戰(zhàn)的頂點順序已由程序代碼本身決定了，所以最終結(jié)果只能輸出該有向圖 的一個拓撲序列，如圖 7-3 所示。 對圖 7-4 所示的有向圖進行拓撲排序，由于圖中存在回路，則無法得到拓撲序列，如圖 7-5 所示。 01 23 圖 7-4 圖 7-5 實驗總結(jié)： 本次試驗通過對有向圖進行拓撲排序，我了解了有向圖的鄰接矩陣和鄰接表的存儲結(jié) 構(gòu)以