c語言算法 - 貪婪算法 - 拓撲排序(2)時間:2010-01-28
2. 數(shù)據(jù)結(jié)構(gòu)的選擇
為將圖1 - 5用C + +代碼來實現(xiàn)，必須考慮序列V的描述方法，以及如何找出可加入V的候選頂點。一種高效的實現(xiàn)方法是將序列V用一維數(shù)組v 來描述的，用一個棧來保存可加入V的候選頂點。另有一個一維數(shù)組I n D e g r e e，I n D e g r e e[ j ]表示與頂點j相連的節(jié)點i 的數(shù)目，其中頂點i不是V中的成員，它們之間的有向圖的邊表示為（ i, j）。當(dāng)I n D e g r e e[ j ]變?yōu)?時表示j 成為一個候選節(jié)點。序列V初始時為空。I n D e g r e e[ j ]為頂點j 的入度。每次向V中加入一個頂點時，所有與新加入頂點鄰接的頂點j，其I n D e g r e e[ j ]減1。對于有向圖1 - 4，開始時I n D e g r e e [ 1 : 6 ]=[ 0 , 0 , 1 , 3 , 1 , 3 ]。由于頂點1和2的I n D e g r e e值為0，因此它們是可加入V的候選頂點，由此，頂點1和2首先入棧。每一步，從棧中取出一個頂點將其加入V，同時減去與其鄰接的頂點的I n D e g r e e值。若在第一步時從棧中取出頂點2并將其加入V，便得到了v [ 0 ]=2，和I n D e g r e e [ 1 : 6 ]=[ 0 , 0 , 1 , 2 , 0 , 3 ]。由于I n D e g r e e [ 5 ]剛剛變?yōu)?，因此將頂點5入棧。
程序1 3 - 2給出了相應(yīng)的C + +代碼，這個代碼被定義為N e t w o r k的一個成員函數(shù)。而且，它對于有無加權(quán)的有向圖均適用。但若用于無向圖（不論其有無加權(quán)）將會得到錯誤的結(jié)果，因為拓撲排序是針對有向圖來定義的。為解決這個問題，利用同樣的模板來定義成員函數(shù)AdjacencyGraph, AdjacencyWGraph，L i n k e d G r a p h和L i n k e d W G r a p h。這些函數(shù)可重載N e t w o r k中的函數(shù)并可輸出錯誤信息。如果找到拓撲序列，則Topological 函數(shù)返回t r u e；若輸入的有向圖無拓撲序列則返回f a l s e。當(dāng)找到拓撲序列時，將其返回到v [ 0 :n- 1 ]中。
3. Network:Topological 的復(fù)雜性
第一和第三個f o r循環(huán)的時間開銷為(n )。若使用（耗費）鄰接矩陣,則第二個for 循環(huán)所用的時間為(n2 )；若使用鄰接鏈表,則所用時間為(n+e)。在兩個嵌套的while 循環(huán)中，外層循環(huán)需執(zhí)行n次，每次將頂點w 加入到v 中，并初始化內(nèi)層while 循環(huán)。使用鄰接矩陣時，內(nèi)層w h i l e循環(huán)對于每個頂點w 需花費(n)的時間；若利用鄰接鏈表，則這個循環(huán)需花費dwout 的時間，因此，內(nèi)層while 循環(huán)的時間開銷為(n2 )或(n+e)。所以，若利用鄰接矩陣，程序1 3 - 2的時間復(fù)雜性為(n2 )，若利用鄰接鏈表則為(n+e)。
程序13-2 拓撲排序
bool Network::Topological(int v[])
{// 計算有向圖中頂點的拓撲次序
// 如果找到了一個拓撲次序，則返回t r u e，此時，在v [ 0 : n - 1 ]中記錄拓撲次序
// 如果不存在拓撲次序，則返回f a l s e
int n=Ve r t i c e s ( ) ;
// 計算入度
int *InDegree=new int [n+1];
InitializePos(); // 圖遍歷器數(shù)組
for (int i=1; i <= n; i++) // 初始化
InDegree[i]=0;
for (i=1; i <= n; i++) {// 從i 出發(fā)的邊
int u=Begin(i);
while (u) {
I n D e g r e e [ u ] + + ;
u=NextVe r t e x ( i ) ; }
}
// 把入度為０的頂點壓入堆棧
LinkedStack S;
for (i=1; i <= n; i++)
if (!InDegree[i]) S.Add(i);
// 產(chǎn)生拓撲次序
i=0; // 數(shù)組v 的游標(biāo)
while (!S.IsEmpty()) {// 從堆棧中選擇
int w; // 下一個頂點
S . D e l e t e ( w ) ;
v[i++]=w;
int u=Begin(w);
while (u) {// 修改入度
I n D e g r e e [ u ] - - ;
if (!InDegree[u]) S.Add(u);
u=NextVe r t e x ( w ) ; }
}
D e a c t i v a t e P o s ( ) ;
delete [] InDegree;
return (i== n);
}
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點擊舉報。
