1、2022/9/15113.3 圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)；然后依次從V0的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止（問(wèn)題：什么時(shí)候會(huì)出現(xiàn)這種情況？）V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7類似于：樹(shù)的前序遍歷！2022/9/152V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7深度遍歷

2、：V1 V2 V4 V8 V5 V6 V3 V72022/9/153V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V3 V6 V7 V52022/9/154深度優(yōu)先遍歷算法遞歸算法開(kāi)始訪問(wèn)v,置標(biāo)志求v鄰接點(diǎn)有鄰接點(diǎn)u求下一鄰接點(diǎn)uvu訪問(wèn)過(guò)結(jié)束NYNYDFS開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)DFSVi=Vi+1Vi=Vexnums結(jié)束NNYY2022/9/155V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V

3、7 V6 V2 V5 V8 V42022/9/156V1V2V4V5V3V7V6V8例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍歷：V1V3 V7 V6 V2 V4 V8 V52022/9/157typedef struct node int adjvex; /鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置 struct node *next; /鏈域，指示下一條邊或弧JD;表頭接點(diǎn)：typedef struct tnode int vexdata; /存放頂點(diǎn)信息 struct node *firstarc;

4、/指示第一個(gè)鄰接點(diǎn)TD;TD gaM; /ga0不用2022/9/158void traver(TD g,int n) int i; static int visitedM; for(i=1;i=n;i+) visitedi=0; for(i=1;iadjvex; if(visitedi=0) dfs(g,i,visited); w=w-next; 2022/9/151013.3 圖的遍歷廣度優(yōu)先搜索(BFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)V0的各個(gè)未曾訪問(wèn)過(guò)的鄰接頂點(diǎn)；然后分別從這些鄰接頂點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚

5、有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8類似于：樹(shù)的層次遍歷！2022/9/1511V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V82022/9/1512V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V52022/9/1513廣度優(yōu)先遍歷算法開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)BFS

6、Vi=Vi+1Vi=Vexnums結(jié)束NNYY2022/9/1514開(kāi)始訪問(wèn)v置標(biāo)志求w鄰接點(diǎn)uu存在嗎w下一鄰接點(diǎn)uu訪問(wèn)過(guò)結(jié)束NYNYBFS初始化隊(duì)列v入隊(duì)隊(duì)列空嗎隊(duì)頭w出隊(duì)訪問(wèn)u,置標(biāo)志u入隊(duì)NaaY2022/9/1515例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列：10 1 2 3 4 54fr遍歷序列：1 40 1 2 3 4 54 3fr遍歷序列：1 4 32022/9/1516例1423512341342vexdatafirstarc 5 5 4 3adjve

7、xnext55 1 5 1 1 4 3 2 20 1 2 3 4 54 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍歷序列：1 4 3 2 52022/9/15170 1 2 3 4 5 2 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 fr遍歷序列：1 4 3 2 5例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 22022/9/1518void trave

8、r(TD g,int n) int i; static int visitedM; for(i=1;i=n;i+) visitedi=0; for(i=1;i=n;i+) if(visitedi=0) bfs(g,i,visited); 2022/9/1519void bfs(TD g,int v,int visited) int quM,f=0,r=0; JD *p; printf(%dn,v); visitedv=1; qu0=v; while(fadjvex; if(visitedv=0) visitedv=1; printf(%dn,v); qu+r=v; p=p-next; 2022

9、/9/152013.4 最短路徑問(wèn)題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問(wèn)題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中， 各邊上權(quán)值之和最小的一條路徑最短路徑單源最短路徑51643208562301371732913長(zhǎng)度最短路徑8131921202022/9/1521Dijkstra算法思想按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，保證：（1）從源點(diǎn)V0到S中各頂點(diǎn)的

10、最短路徑長(zhǎng)度都不大于 從V0到T中任何頂點(diǎn)的最短路徑長(zhǎng)度 （2）每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值 S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長(zhǎng)度 T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間 頂點(diǎn)的最短路徑長(zhǎng)度依據(jù)：可以證明V0到T中頂點(diǎn)Vk的最短路徑，或是從V0到Vk的 直接路徑的權(quán)值；或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和2022/9/1522求最短路徑步驟初使時(shí)令 S=V0,T=其余頂點(diǎn)，T中頂點(diǎn)對(duì)應(yīng)的距離值若存在，距離值為弧上的權(quán)值若不存在，距離值為從T中選取一個(gè)其距離值為最小的頂點(diǎn)W，加入S對(duì)T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復(fù)上

11、述步驟，直到S中包含所有頂點(diǎn)，即S=V為止2022/9/1523void shortpath_DIJ(int adM,int k,int pre, int dist,int n) int i,j,p,wm; k=k-1; for(i=0;in;i+) disti=adki; if(distiMAX) prei=k+1; else prei=0; prek=0; distk=0; adkk=1; for(j=0;j(n-1);j+) wm=MAX; p=-1; for(i=0;in;i+) if(adii=0)&(distiwm) p=i; wm=disti; if(p=-1) break; e

12、lse adpp=1; for(i=0;in;i+) if(adii=0) if(distp+adpidisti) disti=distp+adpi; prei=p+1; 2022/9/1524迭代Sudist2dist3dist4dist5初始1-103010011,2210603010021,2,441050309031,2,4,331050306041,2,4,3,55105030602022/9/1525算法描述算法分析：T(n)=O(n)算法實(shí)現(xiàn)圖用帶權(quán)鄰接矩陣存儲(chǔ)a 數(shù)組dist存放當(dāng)前找到的從源點(diǎn)V0到每個(gè)終點(diǎn)的最短路徑長(zhǎng)度，其初態(tài)為圖中直接路徑權(quán)值數(shù)組pre表示從V0到各終點(diǎn)的

13、最短路徑上，此頂點(diǎn)的前一頂點(diǎn)的序號(hào)；若從V0到某終點(diǎn)無(wú)路徑，則用0作為其前一頂點(diǎn)的序號(hào)2022/9/1526所有頂點(diǎn)對(duì)之間的最短路徑方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次 T(n)=O(n)方法二： Floyd算法算法思想：逐個(gè)頂點(diǎn)試探法求最短路徑步驟初始時(shí)設(shè)置一個(gè)n階方陣，令其對(duì)角線元素為0，若存在弧，則對(duì)應(yīng)元素為權(quán)值；否則為逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值所有頂點(diǎn)試探完畢，算法結(jié)束2022/9/1527例ACB2643110 4 116 0 23 0初始：路徑：AB ACBA BCCA0 4 66 0 23 7 0

14、加入B：路徑：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入A：路徑：AB ACBA BCCA CAB0 4 65 0 23 7 0加入C：路徑：AB ABCBCA BCCA CAB0 0 00 0 00 0 0path=0 0 00 0 00 1 0path=0 0 20 0 00 1 0path=0 0 23 0 00 1 0path=2022/9/1528void shortpath_FLOYD(int costM,int pathM,int lengthM,int n) int i,j,k,wm; for(i=0;in;i+) for(j=0;jn;j+) le

15、ngthij=costij; if(i=j) pathij=0; else if(lengthijMAX) pathij=i+1; else pathij=0; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jn;j+) if(lengthik+lengthkjlengthij) lengthij=lengthik+lengthkj; pathij=pathkj; 2022/9/1529算法實(shí)現(xiàn)圖用鄰接矩陣存儲(chǔ)二維數(shù)組c存放最短路徑長(zhǎng)度pathij是從Vi到Vj的最短路徑上Vj前一頂點(diǎn)序號(hào)算法描述算法分析：T(n)=O(n)實(shí)際上，從實(shí)現(xiàn)代碼來(lái)看： Floyd算法

16、的代碼比用Dijkstra算法要簡(jiǎn)明得多！這樣看來(lái)， Floyd算法似乎沒(méi)帶來(lái)更多的好處？！2022/9/153013.5 生成樹(shù)生成樹(shù)定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫說(shuō)明：一個(gè)圖可以有許多棵不同的生成樹(shù)所有生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹(shù)是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n-1條邊生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹(shù)中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)GHKI2022/9/1531最小生成樹(shù)問(wèn)題提出要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)表示城市權(quán)城市間建立通信線路所需花費(fèi)代價(jià)希望找到一棵生成樹(shù)，它

17、的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小最小代價(jià)生成樹(shù)問(wèn)題分析1654327131791812752410n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路問(wèn)題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把 所有城市（頂點(diǎn)）均連起來(lái)，且總耗費(fèi) （各邊權(quán)值之和）最小2022/9/1532最小生成樹(shù)性質(zhì)用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。本節(jié)介紹的構(gòu)造最小生成樹(shù)的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹(shù)性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，

18、U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹(shù)，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。 2022/9/1533MST性質(zhì)證明 圖示 含邊(u,v)的圈假設(shè)G的任何一棵最小生成樹(shù)都不含邊(u,v)。將邊(u,v)添加到G的一棵最小生成樹(shù)T上，將產(chǎn)生含有邊(u,v)的圈，并且在這個(gè)圈上有一條不同于(u,v)的邊(u,v)，使得uU,vV-U，如下圖所示。 將邊(u,v)刪去，得到G的另一棵生成樹(shù)T。由于cuvcuv，所以T的耗費(fèi)T的耗費(fèi)。于是T是一棵含有邊(u,v)的最小生成樹(shù)，這與假設(shè)矛盾。 2

19、022/9/1534構(gòu)造最小生成樹(shù)方法方法一：Prim算法算法思想：設(shè)G=(V,E)是連通網(wǎng)，T是N上最小生成樹(shù)中邊的集合初始令U=u0,(u0V), T=在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)將(u0,v0)并入集合T，同時(shí)v0并入U(xiǎn)重復(fù)上述操作直至U=V為止，則T=(V, T)為N的最小生成樹(shù)算法實(shí)現(xiàn)：圖用鄰接矩陣表示算法描述算法評(píng)價(jià)：T(n)=O(n)2022/9/1535#define M 30#define MAX 100void minispantree_PRIM(int adM,int n) int i,j,k,p,q,wm; q=p=n-1;

20、adqq=1; for(k=0;k(n-1);k+) wm=MAX; for(i=0;in;i+) if(adii=1) for(j=0;jn;j+) if(adjj=0)&(adijq) adpq=-adpq; else adqp=-adqp; 2022/9/1536例16543265135664251311631416431421164321425165432142532022/9/1537方法二：Kruskal算法算法思想：設(shè)G=(V,E)，令最小生成樹(shù)初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V,)，每個(gè)頂點(diǎn)自成一個(gè)連通分量在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分

21、量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止例1654326513566425165432123452022/9/1538頂點(diǎn)結(jié)點(diǎn)：typedef struct int data; /頂點(diǎn)信息 int jihe; VEX;邊結(jié)點(diǎn)：typedef struct int vexh, vext; /邊依附的兩頂點(diǎn) int weight; /邊的權(quán)值 int flag; /標(biāo)志域EDGE;2022/9/1539void minitree_KRUSKAL(void) int n,i,m,min,k,j; VEX tM; EDGE eM;

22、 printf(Input number of vertex and edge:); scanf(%d,%d,&n,&m); for(i=1;i=n;i+) printf(t%d.data=:,i);scanf(%d,&ti.data);ti.jihe=i; for(i=0;im;i+) printf(vexh,vext,weight:);scanf(%d,%d,%d,&ei.vexh,&ei.vext,&ei.weight);ei.flag=0; i=1;2022/9/1540 while(in) min=MAX;for(j=0;jm;j+) if(ej.weightmin & ej.fla

23、g=0) min=ej.weight; k=j; if(tek.vexh.jihe!=tek.vext.jihe) ek.flag=1; for(j=1;j=n;j+)if(tj.jihe=tek.vext.jihe) tj.jihe=tek.vexh.jihe; tek.vext.jihe=tek.vexh.jihe; i+;else ek.flag=2; for(i=0;im;i+) if(ei.flag=1) printf(%d,%d :%dn,ei.vexh,ei.vext,ei.weight);2022/9/1541算法描述：Prim算法與Kruskal算法的比較 從算法的時(shí)間復(fù)雜性

24、看: 當(dāng)e= (n2)時(shí)，Kruskal算法比Prim算法差，但當(dāng)e= o(n2)時(shí)，Kruskal算法卻比Prim算法好得多。算法分析： 設(shè)輸入的連通賦權(quán)圖有e條邊，則將這些邊依其權(quán)值組成優(yōu)先隊(duì)列需要O(e)時(shí)間；while循環(huán)中，DeleteMin運(yùn)算需要O(loge)時(shí)間，因此關(guān)于優(yōu)先隊(duì)列所作運(yùn)算的時(shí)間為O(eloge)。 實(shí)現(xiàn)UnionFind所需的時(shí)間為O(eloge)。 Kruskal算法所需的計(jì)算時(shí)間是O(eloge)。2022/9/154213.8 拓?fù)渑判騿?wèn)題提出：學(xué)生選修課程問(wèn)題頂點(diǎn)表示課程有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些

25、課程，才能無(wú)矛盾、順利地完成學(xué)業(yè)拓?fù)渑判蚨xAOV網(wǎng)用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex network)，簡(jiǎn)稱AOV網(wǎng)若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件2022/9/1543拓?fù)渑判虬袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過(guò)程叫檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)

26、和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止2022/9/1544例課程代號(hào) 課程名稱 先修棵C1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言語(yǔ)言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C122022/9/1545C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8

27、或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?022/9/1546C1C2C3C4C5C6C7C8C9C10C11C122022/9/1547C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2（2）2022/9/1548C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3（3）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4（4）2022/9/1549C6C8C10C11C12拓?fù)湫蛄校篊1-C2-C3

28、-C4-C5-C7-C9C6C8C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10（8）C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5（5）C6C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7（6）2022/9/1550C6C8C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10-C11（9）C8C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10-C11-C6（10）C8拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12（11）拓?fù)湫蛄校篊1-C2-C3-C4-C

29、5-C7-C9 -C10-C11-C6-C12-C8（12）2022/9/1551算法實(shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤呧徑颖斫Y(jié)點(diǎn)：typedef struct node int vex; /頂點(diǎn)域 struct node *next; /鏈域JD;表頭結(jié)點(diǎn)：typedef struct tnode int in; /入度域 struct node *link; /鏈域TD;TD

30、gM; /g0不用2022/9/1552鄰接表結(jié)點(diǎn)：typedef struct node int vex; /頂點(diǎn)域 struct node *next; /鏈域JD;表頭結(jié)點(diǎn)：typedef struct tnode int in; /入度域 struct node *link; /鏈域TD;TD gM; /g0不用2022/9/1553typedef struct node int vex; struct node *next;JD;typedef struct tnode int vexdata; int in; struct node *link;TD;2022/9/1554void

31、 toposort(TD g,int n) int top,m,k,j,sM; JD *p; top=0; m=0; for(j=1;j0) j=s-top; printf(%d ,gj.vexdata); m+; p=gj.link; while(p!=NULL) k=p-vex; gk.in-; if(gk.in=0) stop+=k; p=p-next; printf(nm=%dn,m); if(mn) printf(The network has a cyclen);2022/9/155532104算法描述例1234560122inlink 5 5 4 3vexnext3 2 5 2

32、40123456top16toptop2022/9/15560122inlink 5 5 4 3vexnext3 2 5 2 40123456輸出序列：63210416toptop2022/9/15570122inlink 5 5 4 3vexnext3 2 5 2 40123456輸出序列：6321041topp2022/9/15580122inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6321041topp2022/9/15590122inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6321041topp2022/9

33、/15600112inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6321041topp2022/9/15610112inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6321041topp=NULL2022/9/15620112inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 1321041toptop2022/9/15630112inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104topp2022/9/15640102inlink 5

34、5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104topp42022/9/15650102inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104p4top2022/9/15660102inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104p4top2022/9/15670002inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104p4top32022/9/15680002inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104p4top32022/9/15690002inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104p4top32022/9/15700001inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104p4top32022/9/15710001inlink 5 5 4 3vexnext2 2 5 2 40123456輸出序列：6 132104p=NULL4top32022/9/15720001inlink 5 5 4 3vexnext2 2