排序算法有很多，所以在特定情景中使用哪一種算法很重要。為了選擇合適的算法，可以按照建議的順序考慮以下標(biāo)準(zhǔn)：
合川網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),合川網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為合川上1000家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的合川做網(wǎng)站的公司定做！
（1）執(zhí)行時(shí)間
（2）存儲(chǔ)空間
（3）編程工作
對(duì)于數(shù)據(jù)量較小的情形，（1）（2）差別不大，主要考慮（3）；而對(duì)于數(shù)據(jù)量大的，（1）為首要。
主要排序法有：
一、冒泡（Bubble）排序——相鄰交換
二、選擇排序——每次最小/大排在相應(yīng)的位置
三、插入排序——將下一個(gè)插入已排好的序列中
四、殼（Shell）排序——縮小增量
五、歸并排序
六、快速排序
七、堆排序
八、拓?fù)渑判?/p>
一、冒泡（Bubble）排序
----------------------------------Code 從小到大排序n個(gè)數(shù)------------------------------------
void BubbleSortArray()
{
for(int i=1;in;i++)
{
for(int j=0;in-i;j++)
{
if(a[j]a[j+1])//比較交換相鄰元素
{
int temp;
temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
}
}
}
}
-------------------------------------------------Code------------------------------------------------
效率 O（n2）,適用于排序小列表。
二、選擇排序
----------------------------------Code 從小到大排序n個(gè)數(shù)--------------------------------
void SelectSortArray()
{
int min_index;
for(int i=0;in-1;i++)
{
min_index=i;
for(int j=i+1;jn;j++)//每次掃描選擇最小項(xiàng)
if(arr[j]arr[min_index]) min_index=j;
if(min_index!=i)//找到最小項(xiàng)交換，即將這一項(xiàng)移到列表中的正確位置
{
int temp;
temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
}
}
}
-------------------------------------------------Code-----------------------------------------
效率O（n2），適用于排序小的列表。
三、插入排序
--------------------------------------------Code 從小到大排序n個(gè)數(shù)-------------------------------------
void InsertSortArray()
{
for(int i=1;in;i++)//循環(huán)從第二個(gè)數(shù)組元素開始，因?yàn)閍rr[0]作為最初已排序部分
{
int temp=arr[i];//temp標(biāo)記為未排序第一個(gè)元素
int j=i-1;
while (j=0 arr[j]temp)/*將temp與已排序元素從小到大比較，尋找temp應(yīng)插入的位置*/
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
}
------------------------------Code--------------------------------------------------------------
最佳效率O（n）；最糟效率O（n2）與冒泡、選擇相同，適用于排序小列表
若列表基本有序，則插入排序比冒泡、選擇更有效率。
四、殼（Shell）排序——縮小增量排序
-------------------------------------Code 從小到大排序n個(gè)數(shù)-------------------------------------
void ShellSortArray()
{
for(int incr=3;incr0;incr--)//增量遞減，以增量3，2，1為例
{
for(int L=0;L(n-1)/incr;L++)//重復(fù)分成的每個(gè)子列表
{
for(int i=L+incr;in;i+=incr)//對(duì)每個(gè)子列表應(yīng)用插入排序
{
int temp=arr[i];
int j=i-incr;
while(j=0arr[j]temp)
{
arr[j+incr]=arr[j];
j-=incr;
}
arr[j+incr]=temp;
}
}
}
}
--------------------------------------Code-------------------------------------------
適用于排序小列表。
效率估計(jì)O（nlog2^n）~O（n^1.5），取決于增量值的最初大小。建議使用質(zhì)數(shù)作為增量值，因?yàn)槿绻隽恐凳?的冪，則在下一個(gè)通道中會(huì)再次比較相同的元素。
殼（Shell）排序改進(jìn)了插入排序，減少了比較的次數(shù)。是不穩(wěn)定的排序，因?yàn)榕判蜻^(guò)程中元素可能會(huì)前后跳躍。
五、歸并排序
----------------------------------------------Code 從小到大排序---------------------------------------
void MergeSort(int low,int high)
{
if(low=high) return;//每個(gè)子列表中剩下一個(gè)元素時(shí)停止
else int mid=(low+high)/2;/*將列表劃分成相等的兩個(gè)子列表,若有奇數(shù)個(gè)元素，則在左邊子列表大于右側(cè)子列表*/
MergeSort(low,mid);//子列表進(jìn)一步劃分
MergeSort(mid+1,high);
int [] B=new int [high-low+1];//新建一個(gè)數(shù)組，用于存放歸并的元素
for(int i=low,j=mid+1,k=low;i=mid j=high;k++)/*兩個(gè)子列表進(jìn)行排序歸并，直到兩個(gè)子列表中的一個(gè)結(jié)束*/
{
if (arr[i]=arr[j];)
{
B[k]=arr[i];
I++;
}
else
{ B[k]=arr[j]; j++; }
}
for( ;j=high;j++,k++)//如果第二個(gè)子列表中仍然有元素，則追加到新列表
B[k]=arr[j];
for( ;i=mid;i++,k++)//如果在第一個(gè)子列表中仍然有元素，則追加到新列表中
B[k]=arr[i];
for(int z=0;zhigh-low+1;z++)//將排序的數(shù)組B的 所有元素復(fù)制到原始數(shù)組arr中
arr[z]=B[z];
}
-----------------------------------------------------Code---------------------------------------------------
效率O（nlogn），歸并的最佳、平均和最糟用例效率之間沒有差異。
適用于排序大列表，基于分治法。
六、快速排序
------------------------------------Code--------------------------------------------
/*快速排序的算法思想：選定一個(gè)樞紐元素，對(duì)待排序序列進(jìn)行分割，分割之后的序列一個(gè)部分小于樞紐元素，一個(gè)部分大于樞紐元素，再對(duì)這兩個(gè)分割好的子序列進(jìn)行上述的過(guò)程。*/ void swap(int a,int b){int t;t =a ;a =b ;b =t ;}
int Partition(int [] arr,int low,int high)
{
int pivot=arr[low];//采用子序列的第一個(gè)元素作為樞紐元素
while (low high)
{
//從后往前栽后半部分中尋找第一個(gè)小于樞紐元素的元素
while (low high arr[high] = pivot)
{
--high;
}
//將這個(gè)比樞紐元素小的元素交換到前半部分
swap(arr[low], arr[high]);
//從前往后在前半部分中尋找第一個(gè)大于樞紐元素的元素
while (low high arr [low ]=pivot )
{
++low ;
}
swap (arr [low ],arr [high ]);//將這個(gè)樞紐元素大的元素交換到后半部分
}
return low ;//返回樞紐元素所在的位置
}
void QuickSort(int [] a,int low,int high)
{
if (low high )
{
int n=Partition (a ,low ,high );
QuickSort (a ,low ,n );
QuickSort (a ,n +1,high );
}
}
----------------------------------------Code-------------------------------------
平均效率O（nlogn），適用于排序大列表。
此算法的總時(shí)間取決于樞紐值的位置；選擇第一個(gè)元素作為樞紐，可能導(dǎo)致O（n2）的最糟用例效率。若數(shù)基本有序，效率反而最差。選項(xiàng)中間值作為樞紐，效率是O（nlogn）。
基于分治法。
七、堆排序
最大堆：后者任一非終端節(jié)點(diǎn)的關(guān)鍵字均大于或等于它的左、右孩子的關(guān)鍵字，此時(shí)位于堆頂?shù)墓?jié)點(diǎn)的關(guān)鍵字是整個(gè)序列中最大的。
思想：
(1)令i=l,并令temp＝ kl ;
(2)計(jì)算i的左孩子j=2i+1;
(3)若j＝n－1，則轉(zhuǎn)(4),否則轉(zhuǎn)(6);
(4)比較kj和kj+1,若kj+1kj,則令j＝j(luò)＋1，否則j不變；
(5)比較temp和kj，若kjtemp，則令ki等于kj，并令i=j,j=2i+1,并轉(zhuǎn)(3),否則轉(zhuǎn)(6)
(6)令ki等于temp，結(jié)束。
-----------------------------------------Code---------------------------
void HeapSort(SeqIAst R)
{ //對(duì)R[1..n]進(jìn)行堆排序，不妨用R[0]做暫存單元 int I; BuildHeap(R)； //將R[1-n]建成初始堆for(i=n;i1；i--) //對(duì)當(dāng)前無(wú)序區(qū)R[1..i]進(jìn)行堆排序，共做n-1趟。{ R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; //將堆頂和堆中最后一個(gè)記錄交換 Heapify(R,1,i-1); //將R[1..i-1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì) } } ---------------------------------------Code--------------------------------------
堆排序的時(shí)間，主要由建立初始堆和反復(fù)重建堆這兩部分的時(shí)間開銷構(gòu)成，它們均是通過(guò)調(diào)用Heapify實(shí)現(xiàn)的。
堆排序的最壞時(shí)間復(fù)雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。 由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。 堆排序是就地排序，輔助空間為O(1)， 它是不穩(wěn)定的排序方法。
堆排序與直接插入排序的區(qū)別:
直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進(jìn)行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實(shí)上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過(guò)，但由于前一趟排序時(shí)未保留這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作。
堆排序可通過(guò)樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。
八、拓?fù)渑判?/p>
例 ：學(xué)生選修課排課先后順序
拓?fù)渑判颍喊延邢驁D中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過(guò)程。
方法：
在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出
從圖中刪除該頂點(diǎn)和所有以它為尾的弧
重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出（拓?fù)渑判虺晒Γ?，或者?dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)（圖中有回路）為止。
---------------------------------------Code--------------------------------------
void TopologicalSort()/*輸出拓?fù)渑判蚝瘮?shù)。若G無(wú)回路，則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K，否則返回ERROR*/
{
int indegree[M];
int i,k,j;
char n;
int count=0;
Stack thestack;
FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度indegree[0....num]
InitStack(thestack);//初始化棧
for(i=0;iG.num;i++)
Console.WriteLine("結(jié)點(diǎn)"+G.vertices[i].data+"的入度為"+indegree[i]);
for(i=0;iG.num;i++)
{
if(indegree[i]==0)
Push(thestack.vertices[i]);
}
Console.Write("拓?fù)渑判蜉敵鲰樞驗(yàn)椋?);
while(thestack.Peek()!=null)
{
Pop(thestack.Peek());
j=locatevex(G,n);
if (j==-2)
{
Console.WriteLine("發(fā)生錯(cuò)誤，程序結(jié)束。");
exit();
}
Console.Write(G.vertices[j].data);
count++;
for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)
{
k=p.adjvex;
if (!(--indegree[k]))
Push(G.vertices[k]);
}
}
if (countG.num)
Cosole.WriteLine("該圖有環(huán)，出現(xiàn)錯(cuò)誤，無(wú)法排序。");
else
Console.WriteLine("排序成功。");
}
----------------------------------------Code--------------------------------------
算法的時(shí)間復(fù)雜度O（n+e）。
*/
#include stdio.h
#include malloc.h
// 輸出有向圖的一個(gè)拓?fù)湫蛄小?shí)現(xiàn)算法7.12的程序
// 圖的鄰接表存儲(chǔ)表示
#define MAX_NAME 3 // 頂點(diǎn)字符串的最大長(zhǎng)度+1
#define MAX_VERTEX_NUM 20
typedef int InfoType; // 存放網(wǎng)的權(quán)值
typedef char VertexType[MAX_NAME]; // 字符串類型
typedef enum{DG,DN,AG,AN}GraphKind; // {有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)}
typedef struct ArcNode
{
int adjvex; // 該弧所指向的頂點(diǎn)的位置
struct ArcNode *nextarc; // 指向下一條弧的指針
InfoType *info; // 網(wǎng)的權(quán)值指針）
}ArcNode; // 表結(jié)點(diǎn)
typedef struct VNode
{
VertexType data; // 頂點(diǎn)信息
ArcNode *firstarc; // 第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM];// 頭結(jié)點(diǎn)
typedef struct
{
AdjList vertices;
int vexnum,arcnum; // 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)
int kind; // 圖的種類標(biāo)志
}ALGraph;
// 若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1。
int LocateVex(ALGraph G,VertexType u)
{
int i;
for(i=0;iG.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
// 采用鄰接表存儲(chǔ)結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖G(用一個(gè)函數(shù)構(gòu)造4種圖)。
int CreateGraph(ALGraph *G)
{
int i,j,k;
int w; // 權(quán)值
VertexType va,vb;
ArcNode *p;
printf("請(qǐng)輸入圖的類型(有向圖:0,有向網(wǎng):1,無(wú)向圖:2,無(wú)向網(wǎng):3): ");
scanf("%d",(*G).kind);
printf("請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù):（空格）\n");
scanf("%d%d", (*G).vexnum, (*G).arcnum);
printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的值(%d個(gè)字符):\n",(*G).vexnum,MAX_NAME);
for(i = 0; i (*G).vexnum; ++i) // 構(gòu)造頂點(diǎn)向量
{
scanf("%s", (*G).vertices[i].data);
(*G).vertices[i].firstarc = NULL;
}
if((*G).kind == 1 || (*G).kind == 3) // 網(wǎng)
printf("請(qǐng)順序輸入每條弧(邊)的權(quán)值、弧尾和弧頭(以空格作為間隔):\n");
else // 圖
printf("請(qǐng)順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");
for(k = 0;k (*G).arcnum; ++k) // 構(gòu)造表結(jié)點(diǎn)鏈表
{
if((*G).kind==1||(*G).kind==3) // 網(wǎng)
scanf("%d%s%s",w,va,vb);
else // 圖
scanf("%s%s",va,vb);
i = LocateVex(*G,va); // 弧尾
j = LocateVex(*G,vb); // 弧頭
p = (ArcNode*)malloc(sizeof(ArcNode));
p-adjvex = j;
if((*G).kind == 1 || (*G).kind == 3) // 網(wǎng)
{
p-info = (int *)malloc(sizeof(int));
*(p-info) = w;
}
else
p-info = NULL; // 圖
p-nextarc = (*G).vertices[i].firstarc; // 插在表頭
(*G).vertices[i].firstarc = p;
if((*G).kind = 2) // 無(wú)向圖或網(wǎng),產(chǎn)生第二個(gè)表結(jié)點(diǎn)
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p-adjvex = i;
if((*G).kind == 3) // 無(wú)向網(wǎng)
{
p-info = (int*)malloc(sizeof(int));
*(p-info) = w;
}
else
p-info = NULL; // 無(wú)向圖
p-nextarc = (*G).vertices[j].firstarc; // 插在表頭
(*G).vertices[j].firstarc = p;
}
}
return 1;
}
// 輸出圖的鄰接表G。
void Display(ALGraph G)
{
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向圖\n");
break;
case DN: printf("有向網(wǎng)\n");
break;
case AG: printf("無(wú)向圖\n");
break;
case AN: printf("無(wú)向網(wǎng)\n");
}
printf("%d個(gè)頂點(diǎn)：\n",G.vexnum);
for(i = 0; i G.vexnum; ++i)
printf("%s ",G.vertices[i].data);
printf("\n%d條弧(邊):\n", G.arcnum);
for(i = 0; i G.vexnum; i++)
{
p = G.vertices[i].firstarc;
while(p)
{
if(G.kind = 1) // 有向
{
printf("%s→%s ",G.vertices[i].data,
G.vertices[p-adjvex].data);
if(G.kind == DN) // 網(wǎng)
printf(":%d ", *(p-info));
}
else // 無(wú)向(避免輸出兩次)
{
if(i p-adjvex)
{
printf("%s－%s ",G.vertices[i].data,
G.vertices[p-adjvex].data);
if(G.kind == AN) // 網(wǎng)
printf(":%d ",*(p-info));
}
}
p=p-nextarc;
}
printf("\n");
}
}
// 求頂點(diǎn)的入度，算法7.12、7.13調(diào)用
void FindInDegree(ALGraph G,int indegree[])
{
int i;
ArcNode *p;
for(i=0;iG.vexnum;i++)
indegree[i]=0; // 賦初值
for(i=0;iG.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p-adjvex]++;
p=p-nextarc;
}
}
}
typedef int SElemType; // 棧類型
#define STACK_INIT_SIZE 10 // 存儲(chǔ)空間初始分配量
#define STACKINCREMENT 2 // 存儲(chǔ)空間分配增量
// 棧的順序存儲(chǔ)表示 P46
typedef struct SqStack
{
SElemType *base; // 在棧構(gòu)造之前和銷毀之后，base的值為NULL
SElemType *top; // 棧頂指針
int stacksize; // 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位
}SqStack; // 順序棧
// 構(gòu)造一個(gè)空棧S。
int InitStack(SqStack *S)
{
// 為棧底分配一個(gè)指定大小的存儲(chǔ)空間
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if( !(*S).base )
exit(0); // 存儲(chǔ)分配失敗
(*S).top = (*S).base; // 棧底與棧頂相同表示一個(gè)空棧
(*S).stacksize = STACK_INIT_SIZE;
return 1;
}
// 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。
int StackEmpty(SqStack S)
{
if(S.top == S.base)
return 1;
else
return 0;
}
// 插入元素e為新的棧頂元素。
int Push(SqStack *S, SElemType e)
{
if((*S).top - (*S).base = (*S).stacksize) // 棧滿，追加存儲(chǔ)空間
{
(*S).base = (SElemType *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
if( !(*S).base )
exit(0); // 存儲(chǔ)分配失敗
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++=e;
// 這個(gè)等式的++ * 優(yōu)先級(jí)相同，但是它們的運(yùn)算方式，是自右向左
return 1;
}
// 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。
int Pop(SqStack *S,SElemType *e)
{
if((*S).top == (*S).base)
return 0;
*e = *--(*S).top;
// 這個(gè)等式的++ * 優(yōu)先級(jí)相同，但是它們的運(yùn)算方式，是自右向左
return 1;
}
// 算法7.12 P182
// 有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無(wú)回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫?/p>
// 列并返回1, 否則返回0。
int TopologicalSort(ALGraph G)
{
int i,k,count,indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G,indegree); // 對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]
InitStack(S); // 初始化棧
for(i=0;iG.vexnum;++i) // 建零入度頂點(diǎn)棧S
if(!indegree[i])
Push(S,i); // 入度為0者進(jìn)棧
count=0; // 對(duì)輸出頂點(diǎn)計(jì)數(shù)
while(!StackEmpty(S))
{
// 棧不空
Pop(S,i);
printf("%s ",G.vertices[i].data); // 輸出i號(hào)頂點(diǎn)并計(jì)數(shù)
++count;
for(p=G.vertices[i].firstarc;p;p=p-nextarc)
{
// 對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1
k=p-adjvex;
if(!(--indegree[k])) // 若入度減為0,則入棧
Push(S,k);
}
}
if(countG.vexnum)
{
printf("此有向圖有回路\n");
return 0;
}
else
{
printf("為一個(gè)拓?fù)湫蛄小n");
return 1;
}
}
int main()
{
ALGraph f;
printf("請(qǐng)選擇有向圖\n");
CreateGraph(f);
Display(f);
TopologicalSort(f);
system("pause");
return 0;
}
/*
輸出效果：
請(qǐng)選擇有向圖
請(qǐng)輸入圖的類型(有向圖:0,有向網(wǎng):1,無(wú)向圖:2,無(wú)向網(wǎng):3): 0
請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù):（空格）
4 4
請(qǐng)輸入4個(gè)頂點(diǎn)的值(3個(gè)字符):
a
b
c
d
請(qǐng)順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):
a b
a c
b d
c d
有向圖
4個(gè)頂點(diǎn)：
a b c d
4條弧(邊):
a→c a→b
b→d
c→d
a b c d 為一個(gè)拓?fù)湫蛄小?/p>
請(qǐng)按任意鍵繼續(xù). . .
*/
public class Arr{
//數(shù)組
int[] arr = {3,1,6,4,5,10,2};
//對(duì)數(shù)組進(jìn)行簡(jiǎn)單的排序
java.util.Arrays.sort(arr);
//輸出最大值、最小值
System.out.println("最大值：" + arr[arr.length-1] +"\n最小值：" + arr[0]);
//從小到大輸出
System.out.println(java.util.Arrays.toString(arr));
}
拓?fù)渑判蚴怯邢驁D的一個(gè)重要操作。在給定的有向圖G中，若頂點(diǎn)序列vi1,vi2,...,vin滿足下列條件：若在有向圖G中從頂點(diǎn)vi到頂點(diǎn)vj有一條路徑，則在序列中頂點(diǎn)vi必在頂點(diǎn)vj之前，便稱這個(gè)序列為一個(gè)拓?fù)湫蛄小Ｇ笠粋€(gè)有向圖拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判颉?/p>
舉例：計(jì)算機(jī)專業(yè)的學(xué)生應(yīng)該學(xué)習(xí)的部分課程及其每門課程所需要的先修課程。
拓?fù)渑判虻姆椒ǎ?/p>
（1）從圖中選擇一個(gè)入度為0的頂點(diǎn)且輸出之；
（2）從圖中刪掉該頂點(diǎn)及其所有以該頂點(diǎn)為弧尾的?。?/p>
反復(fù)執(zhí)行這兩個(gè)步驟，直到所有的頂點(diǎn)都被輸出，輸出的序列就是這個(gè)無(wú)環(huán)有向圖的拓?fù)湫蛄小＜?xì)心的讀者可能會(huì)發(fā)現(xiàn)：在每一時(shí)刻，可能同時(shí)存在多個(gè)入度為0的頂點(diǎn)，選擇注：表中c1~c9列表示的是每個(gè)頂點(diǎn)的入度。
下面我們討論一下如何實(shí)現(xiàn)拓?fù)渑判虻乃惴?。假設(shè)有向圖以鄰接表的形式存儲(chǔ)。
下面給出算法實(shí)現(xiàn)的基本過(guò)程：
{ 將所有入度為0的頂點(diǎn)入棧；
當(dāng)棧非空時(shí)重復(fù)執(zhí)行下列操作：
從棧中退出頂點(diǎn)k；
（1）將k頂點(diǎn)的信息輸出；
（2）將與k鄰接的所有頂點(diǎn)的入度減1。 }#defineMAX_VERTEX_NUM30//最大頂點(diǎn)個(gè)數(shù)typestructEdgeLinklist{//邊結(jié)點(diǎn)intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//頂點(diǎn)結(jié)點(diǎn)Elemtypeelem;intindegree;//記錄頂點(diǎn)的入度EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];下面是拓?fù)渑判虻耐暾惴ā? StatusTopologicalSort(AdjListadj){InitStack(s);for(i=0;iMAX_VERTEX_NUM-1;i++)if(adj.indegree==0)Push(s,i);while(!StackEmpty(s)){Pop(s,i);printf(i);for(p=adj.firstedge;p;p=p-next){adj.indegree-=1;if(adj.indegree==0)Push(s,i);}
重慶分公司
重慶分公司
