寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時(shí)最大的愛(ài)好就是聽(tīng)聽(tīng)歌，逛逛B站。博主很喜歡的一句話花開(kāi)堪折直須折，莫待無(wú)花空折枝：博主的理解是頭一次為人，就應(yīng)該做自己想做的事，做自己不后悔的事，做自己以后不會(huì)留有遺憾的事，做自己覺(jué)得有意義的事，不浪費(fèi)這大好的青春年華。博主寫博客目的是記錄所學(xué)到的知識(shí)并方便自己復(fù)習(xí)，在記錄知識(shí)的同時(shí)獲得部分瀏覽量，得到更多人的認(rèn)可，滿足小小的成就感，同時(shí)在寫博客的途中結(jié)交更多志同道合的朋友，讓自己在技術(shù)的路上并不孤單。

目錄:
1.全序和偏序
2.拓?fù)渑判虻姆椒?br /> 3.拓?fù)渑判駽語(yǔ)言完整代碼實(shí)現(xiàn)
4.拓?fù)渑判蛐〗Y(jié)

1.全序和偏序

拓?fù)渑判蛑傅氖菍⒂邢驘o(wú)環(huán)圖（又稱“DAG”圖）中的頂點(diǎn)按照?qǐng)D中指定的先后順序進(jìn)行排序。

例如，上圖 中的兩個(gè)圖都是有向無(wú)環(huán)圖，都可以使用拓?fù)渑判驅(qū)D中的頂點(diǎn)進(jìn)行排序，兩個(gè)圖形的區(qū)別是：左圖中的 V2 和 V3之間沒(méi)有明確的前后順序；而右圖中任意兩個(gè)頂點(diǎn)之間都有前后順序。

所以，左圖中頂點(diǎn)之間的關(guān)系被稱為“偏序”關(guān)系；右圖中頂點(diǎn)之間的關(guān)系被稱為”全序“關(guān)系。全序是偏序的一種特殊情況。對(duì)于任意一個(gè)有向無(wú)環(huán)圖來(lái)說(shuō)，通過(guò)拓?fù)渑判虻玫降男蛄惺紫纫欢ㄊ瞧?#xff0c;如果任意兩個(gè)頂點(diǎn)都具有前后順序，那么此序列是全序。

2.拓?fù)渑判虻姆椒?/h1>

對(duì)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判?#xff0c;只需要遵循兩個(gè)原則：

在圖中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn) V；

從圖中刪除頂點(diǎn) V 和所有以該頂點(diǎn)為尾的弧

上面左圖拓?fù)渑判蛉缦?#xff1a;

對(duì)于此圖來(lái)說(shuō)，拓?fù)渑判蛴袃煞N：

1.V1 -> V2 -> V3 -> V4
2.V1 -> V3 -> V2 -> V4
如果頂點(diǎn)之間只是具有偏序關(guān)系，那么拓?fù)渑判虻慕Y(jié)果肯定不唯一；如果頂點(diǎn)之間是全序關(guān)系，那么拓?fù)渑判虻玫降男蛄形ㄒ?/strong>

有向無(wú)環(huán)圖如果頂點(diǎn)本身具有某種實(shí)際意義，例如用有向無(wú)環(huán)圖表示大學(xué)期間所學(xué)習(xí)的全部課程，每個(gè)頂點(diǎn)都表示一門課程，有向邊表示課程學(xué)習(xí)的先后次序，例如要先學(xué)《程序設(shè)計(jì)基礎(chǔ)》和《離散數(shù)學(xué)》，然后才能學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》。所以用來(lái)表示某種活動(dòng)間的優(yōu)先關(guān)系的有向圖簡(jiǎn)稱為“AOV 網(wǎng)”。

3.拓?fù)渑判駽語(yǔ)言完整代碼實(shí)現(xiàn)

在編寫程序解決拓?fù)渑判虻膯?wèn)題時(shí)，大致思路為：首先通過(guò)鄰接表將 AOV 網(wǎng)進(jìn)行存儲(chǔ)，由于拓?fù)渑判虻恼麄€(gè)過(guò)程中，都是以頂 點(diǎn)的入度為依據(jù)進(jìn)行排序，所以需要根據(jù)建立的鄰接表統(tǒng)計(jì)出各頂點(diǎn)的入度。 在得到各頂點(diǎn)的入度后，首先找到入度為 0 的頂點(diǎn)作為拓?fù)渑判虻钠鹗键c(diǎn)，然后查找以該頂點(diǎn)為起始點(diǎn)的所有頂點(diǎn)，如果入度 為 1，說(shuō)明如果刪除前一個(gè)頂點(diǎn)后，該頂點(diǎn)的入度為 0，為拓?fù)渑判虻南乱粋€(gè)對(duì)象

#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 20//最大頂點(diǎn)個(gè)數(shù) #define VertexType int//頂點(diǎn)數(shù)據(jù)的類型 typedef enum{false,true} bool; typedef struct ArcNode{int adjvex;//鄰接點(diǎn)在數(shù)組中的位置下標(biāo)struct ArcNode * nextarc;//指向下一個(gè)鄰接點(diǎn)的指針 }ArcNode; typedef struct VNode{VertexType data;//頂點(diǎn)的數(shù)據(jù)域ArcNode * firstarc;//指向鄰接點(diǎn)的指針 }VNode,AdjList[MAX_VERTEX_NUM];//存儲(chǔ)各鏈表頭結(jié)點(diǎn)的數(shù)組 typedef struct {AdjList vertices;//圖中頂點(diǎn)及各鄰接點(diǎn)數(shù)組int vexnum,arcnum;//記錄圖中頂點(diǎn)數(shù)和邊或弧數(shù) }ALGraph; //找到頂點(diǎn)對(duì)應(yīng)在鄰接表數(shù)組中的位置下標(biāo) int LocateVex(ALGraph G,VertexType u){for (int i=0; i<G.vexnum; i++) {if (G.vertices[i].data==u) {return i;}}return -1; } //創(chuàng)建 AOV 網(wǎng)，構(gòu)建鄰接表 void CreateAOV(ALGraph **G){*G=(ALGraph*)malloc(sizeof(ALGraph)); scanf("%d,%d",&((*G)->vexnum),&((*G)->arcnum));for (int i=0; i<(*G)->vexnum; i++) {scanf("%d",&((*G)->vertices[i].data));(*G)->vertices[i].firstarc=NULL;}VertexType initial,end;for (int i=0; i<(*G)->arcnum; i++) { scanf("%d,%d",&initial,&end);ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=LocateVex(*(*G), end);p->nextarc=NULL;int locate=LocateVex(*(*G), initial);p->nextarc=(*G)->vertices[locate].firstarc;(*G)->vertices[locate].firstarc=p;} } //結(jié)構(gòu)體定義棧結(jié)構(gòu) typedef struct stack{VertexType data; struct stack * next; }stack; //初始化棧結(jié)構(gòu) void initStack(stack* *S){ (*S)=(stack*)malloc(sizeof(stack)); (*S)->next=NULL; } //判斷鏈表是否為空 bool StackEmpty(stack S){if (S.next==NULL) { return true;}return false; } //進(jìn)棧，以頭插法將新結(jié)點(diǎn)插入到鏈表中 void push(stack *S,VertexType u){stack *p=(stack*)malloc(sizeof(stack));p->data=u;p->next=NULL;p->next=S->next;S->next=p; } //彈棧函數(shù)，刪除鏈表首元結(jié)點(diǎn)的同時(shí)，釋放該空間，并將該結(jié)點(diǎn)中的數(shù)據(jù)域通過(guò)地址傳值給變量 i; void pop(stack *S,VertexType *i){ stack *p=S->next; *i=p->data;S->next=S->next->next;free(p); } //統(tǒng)計(jì)各頂點(diǎn)的入度 void FindInDegree(ALGraph G,int indegree[]){ //初始化數(shù)組，默認(rèn)初始值全部為 0for (int i=0; i<G.vexnum; i++) {indegree[i]=0;} //遍歷鄰接表，根據(jù)各鏈表中結(jié)點(diǎn)的數(shù)據(jù)域存儲(chǔ)的各頂點(diǎn)位置下標(biāo)，在 indegree 數(shù)組相應(yīng)位置+1for (int i=0; i<G.vexnum; i++) {ArcNode *p=G.vertices[i].firstarc; while (p) {indegree[p->adjvex]++;p=p->nextarc;} } } void TopologicalSort(ALGraph G){int indegree[G.vexnum];//創(chuàng)建記錄各頂點(diǎn)入度的數(shù)組FindInDegree(G,indegree);//統(tǒng)計(jì)各頂點(diǎn)的入度 //建立棧結(jié)構(gòu)，程序中使用的是鏈表stack *S;initStack(&S); //查找度為 0 的頂點(diǎn)，作為起始點(diǎn)for (int i=0; i<G.vexnum; i++) {if (!indegree[i]) {push(S, i);}}int count=0; //當(dāng)棧為空，說(shuō)明排序完成while (!StackEmpty(*S)) {int index; //彈棧，并記錄棧中保存的頂點(diǎn)所在鄰接表數(shù)組中的位置pop(S,&index);printf("%d",G.vertices[index].data);++count; //依次查找跟該頂點(diǎn)相鏈接的頂點(diǎn)，如果初始入度為 1，當(dāng)刪除前一個(gè)頂點(diǎn)后，該頂點(diǎn)入度為 0for (ArcNode *p=G.vertices[index].firstarc; p; p=p->nextarc) {VertexType k=p->adjvex;if (!(--indegree[k])) {//頂點(diǎn)入度為 0，入棧push(S, k);}}} //如果 count 值小于頂點(diǎn)數(shù)量，表明該有向圖有環(huán)if (count<G.vexnum) {printf("該圖有回路"); return;} } int main(){ALGraph *G;CreateAOV(&G);//創(chuàng)建 AOV 網(wǎng)TopologicalSort(*G);//進(jìn)行拓?fù)渑判?/span>return 0; }

對(duì)于下面例子

進(jìn)行拓?fù)渑判?#xff1a;

//輸入 6,8 1 2 3 4 5 6 1,2 1,4 1,3 3,2 3,5 4,5 6,4 6,5 //輸出 6 1 4 3 2 5

4.拓?fù)渑判蛐〗Y(jié)

對(duì)于含有n個(gè)頂點(diǎn)和e條邊的有向圖而言，建立求各個(gè)頂點(diǎn)的入度的時(shí)間復(fù)雜度為O(e);建立0入度頂點(diǎn)棧的時(shí)間復(fù)雜度為O(n),在拓?fù)渑判蛑腥粲邢驁D無(wú)環(huán)，則每個(gè)頂點(diǎn)進(jìn)一次棧出一次棧，所以總的時(shí)間復(fù)雜度為O(n+e)

本篇博客轉(zhuǎn)載C語(yǔ)言中文網(wǎng)

總結(jié)

以上是生活随笔為你收集整理的拓扑排序(完整案列及C语言完整代码实现)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。