拓?fù)渑判?/h2>
AOV網(wǎng)絡(luò)（Activity On Vertex）
拓?fù)湫颍喝绻趫D中從V到W有一條有向路徑，則V一定排在W之前。滿足此條件的頂點(diǎn)序列稱為一個(gè)拓?fù)湫?br>
獲得一個(gè)拓?fù)湫虻倪^程就是拓?fù)渑判?br>
AVO如果有合理的拓?fù)湫颍瑒t必定是有向無環(huán)圖（Directed Acyclic Graph，DAG）
算法：
void TopSort ( )
{
for ( cnt = 0 ; cnt < [ V ] ; cnt ++ ) {
V = 未輸出的入度為0的頂點(diǎn) ;
if ( 這樣的V不存在 ) {
Error ( “圖中有回路” ) ;
break ;
}
輸出V，或者紀(jì)錄V的輸出序號(hào)；
for ( V 的每個(gè)鄰接點(diǎn) W )
Indegree [ W ]－－；
}
}
改進(jìn)：隨時(shí)將入度變?yōu)?的頂點(diǎn)放到一個(gè)容器里
void TopSort ( )
{
for ( 圖中每個(gè)頂點(diǎn) V ) {
if ( Indegree [ W ] == 0 )
Enqueue ( V , Q ) ;
while ( ! IsEmpty ( Q ) ) ;
V = Dequeue ( Q ) ;
輸出V，或者紀(jì)錄V的輸出序號(hào)；
cnt ++; // 計(jì)數(shù)器，紀(jì)錄頂點(diǎn)數(shù)量
for ( V 的每個(gè)鄰接點(diǎn) W )
if ( —Indegree [ W ] == 0 ) //如果減完后入度為0，則將其放入容器中
Enqueue ( W , Q ) ;
}
if ( cnt != [ V ] )
Error ( “圖中有回路” )；
}
時(shí)間復(fù)雜度 T = O( |V| + |E| )
此算法可以用來檢測有向圖是否DAG
關(guān)鍵路徑問題
AOE（Activity On Edge）網(wǎng)絡(luò)
一般用于安排項(xiàng)目的工序，活動(dòng)表示在邊上，頂點(diǎn)代表活動(dòng)的停止；邊上寫有活動(dòng)持續(xù)時(shí)間
頂點(diǎn)包括：頂點(diǎn)編號(hào)、最早完成時(shí)間、最晚完成時(shí)間
兩類基礎(chǔ)算法，排序和查找
排序算法的前提前提：
void X_Sort ( ElementType A [ ], int N )
1.大多數(shù)情況下，為簡單起見，討論從小到大的整數(shù)排序
2.N是正整數(shù)，只討論基于比較的排序（> ＝ < 是有定義的）
3.只討論內(nèi)部排序：內(nèi)存空間充分大，排序在內(nèi)部空間中完成
4.穩(wěn)定性：任意兩個(gè)相等的數(shù)據(jù)，排序前后的相對位置不發(fā)生改變
5.沒有一種排序算法是任何情況下都表現(xiàn)最好的
－簡單排序：
－冒泡排序
void Bubble_Sort ( ElementType A[ ] , int N )
{
for ( P = N - 1 ; P >= 0 ; P — ) {
flag = 0 ;
for ( i = 0 ; i < p ; i ++ ) { // 一趟冒泡
if ( A[ i ] > A[ i + 1 ] ) { // 比較相鄰兩個(gè)元素的大小
Swap ( A[ i ] , A[ i + 1 ] ) ;
flag = 1 ; // 標(biāo)識(shí)發(fā)生了交換
}
} // 思考：假設(shè)當(dāng)程序執(zhí)行到某一步時(shí) 數(shù)據(jù)已經(jīng)是有序的了，但此時(shí)程序是不知道的，所以還要判斷
if ( flag == 0 ) break ; // 全程無交換 數(shù)據(jù)已經(jīng)有序 不需要再進(jìn)從排序
}
}
最好情況：順序 T = O ( N )
最壞情況：逆序 T = O ( N的平方 )
由于是單向執(zhí)行，比較相鄰的兩個(gè)元素，所以適用于鏈表存儲(chǔ)的數(shù)據(jù)
當(dāng)兩個(gè)數(shù)據(jù)相等，冒泡排序的比較過程中沒有將它們交換位置，所以改算法是穩(wěn)定的
－插入排序
void Insertion_Sort ( ElementType A[ ] , int N )
{
for ( P = 1 ; P < N ; P ++ ) // 假設(shè)第0個(gè)元素已經(jīng)存在，從第一個(gè)元素開始插入
{
Tmp = A[ P ] ; // 下一個(gè)元素
for ( i = P ; i > 0 && A[ i - 1 ] > Tmp ; i -- ) // 需要插入的新元素當(dāng)前從最后那個(gè)元素開始比起，比到第一個(gè)元素
A[ i ] = A[ i - 1 ] ; // 移除空位
A[ i ] = Tmp ; // 新元素落位
}
}
最好情況：順序 T = O ( N )
最壞情況：逆序 T = O ( N的平方 )
冒泡元素是兩兩交換 需要涉及到三步，插入排序元素向后錯(cuò)，新元素一次放入
逆序?qū)Γ簩τ谙聵?biāo) i < j，如果A[ i ] > A[ j ]，則稱 ( i , j )是一對逆序?qū)?br>
每一次交換元素正好消去一個(gè)逆序?qū)?，序列中有多少個(gè)逆序?qū)?，就需要交換幾次元素
時(shí)間復(fù)雜度下界：
插入排序：T( N , I ) = O( N + I ) 其中 I 是逆序?qū)€(gè)數(shù)，如果序列基本有序，則插入排序簡單且高效
定理：任意N個(gè)不同元素組成的序列平均有 N（N－1）／4 個(gè)逆序?qū)Α?br>
定理：任何僅以交換相鄰元素來排序的算法，其平均時(shí)間復(fù)雜度的下界為N平方
要提高算法效率，我們必須：每次交換不止消去一個(gè)逆序?qū)?，所以我們每次交換相隔較遠(yuǎn)的兩個(gè)個(gè)元素
