拓?fù)渑判?/h2>
AOV網(wǎng)絡(luò)（Activity On Vertex）
拓?fù)湫颍喝绻趫D中從V到W有一條有向路徑秒梅，則V一定排在W之前旗芬。滿足此條件的頂點(diǎn)序列稱為一個拓?fù)湫?br>
獲得一個拓?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的輸出序號；
for ( V 的每個鄰接點(diǎn) W )
Indegree [ W ]－－辆它；
}
}
改進(jìn)：隨時將入度變?yōu)?的頂點(diǎn)放到一個容器里
void TopSort ( )
{
for ( 圖中每個頂點(diǎn) V ) {
if ( Indegree [ W ] == 0 )
Enqueue ( V , Q ) ;
while ( ! IsEmpty ( Q ) ) ;
V = Dequeue ( Q ) ;
輸出V誊薄，或者紀(jì)錄V的輸出序號；
cnt ++; // 計數(shù)器锰茉，紀(jì)錄頂點(diǎn)數(shù)量
for ( V 的每個鄰接點(diǎn) W )
if ( —Indegree [ W ] == 0 ) //如果減完后入度為0呢蔫，則將其放入容器中
Enqueue ( W , Q ) ;
}
if ( cnt != [ V ] )
Error ( “圖中有回路” )；
}
時間復(fù)雜度 T = O( |V| + |E| )
此算法可以用來檢測有向圖是否DAG
關(guān)鍵路徑問題
AOE（Activity On Edge）網(wǎng)絡(luò)
一般用于安排項(xiàng)目的工序飒筑，活動表示在邊上片吊，頂點(diǎn)代表活動的停止；邊上寫有活動持續(xù)時間
頂點(diǎn)包括：頂點(diǎn)編號协屡、最早完成時間定鸟、最晚完成時間
兩類基礎(chǔ)算法，排序和查找
排序算法的前提前提：
void X_Sort ( ElementType A [ ], int N )
1.大多數(shù)情況下著瓶，為簡單起見联予，討論從小到大的整數(shù)排序
2.N是正整數(shù)，只討論基于比較的排序（> ＝ < 是有定義的）
3.只討論內(nèi)部排序：內(nèi)存空間充分大材原，排序在內(nèi)部空間中完成
4.穩(wěn)定性：任意兩個相等的數(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 ] ) { // 比較相鄰兩個元素的大小
Swap ( A[ i ] , A[ i + 1 ] ) ;
flag = 1 ; // 標(biāo)識發(fā)生了交換
}
} // 思考：假設(shè)當(dāng)程序執(zhí)行到某一步時 數(shù)據(jù)已經(jīng)是有序的了，但此時程序是不知道的余蟹，所以還要判斷
if ( flag == 0 ) break ; // 全程無交換 數(shù)據(jù)已經(jīng)有序 不需要再進(jìn)從排序
}
}
最好情況：順序 T = O ( N )
最壞情況：逆序 T = O ( N的平方 )
由于是單向執(zhí)行卷胯，比較相鄰的兩個元素，所以適用于鏈表存儲的數(shù)據(jù)
當(dāng)兩個數(shù)據(jù)相等威酒，冒泡排序的比較過程中沒有將它們交換位置窑睁，所以改算法是穩(wěn)定的
－插入排序
void Insertion_Sort ( ElementType A[ ] , int N )
{
for ( P = 1 ; P < N ; P ++ ) // 假設(shè)第0個元素已經(jīng)存在挺峡，從第一個元素開始插入
{
Tmp = A[ P ] ; // 下一個元素
for ( i = P ; i > 0 && A[ i - 1 ] > Tmp ; i -- ) // 需要插入的新元素當(dāng)前從最后那個元素開始比起，比到第一個元素
A[ i ] = A[ i - 1 ] ; // 移除空位
A[ i ] = Tmp ; // 新元素落位
}
}
最好情況：順序 T = O ( N )
最壞情況：逆序 T = O ( N的平方 )
冒泡元素是兩兩交換 需要涉及到三步担钮，插入排序元素向后錯橱赠，新元素一次放入
逆序?qū)Γ簩τ谙聵?biāo) i < j，如果A[ i ] > A[ j ]箫津，則稱 ( i , j )是一對逆序?qū)?br>
每一次交換元素正好消去一個逆序?qū)ο烈蹋蛄兄杏卸嗌賯€逆序?qū)Γ托枰粨Q幾次元素
時間復(fù)雜度下界：
插入排序：T( N , I ) = O( N + I ) 其中 I 是逆序?qū)€數(shù)苏遥，如果序列基本有序饼拍，則插入排序簡單且高效
定理：任意N個不同元素組成的序列平均有 N（N－1）／4 個逆序?qū)Α?br>
定理：任何僅以交換相鄰元素來排序的算法，其平均時間復(fù)雜度的下界為N平方
要提高算法效率田炭，我們必須：每次交換不止消去一個逆序?qū)κΤ晕覀兠看谓粨Q相隔較遠(yuǎn)的兩個個元素
