gabow算法word版(編輯修改稿)
2024-09-13 04:46 本頁面
【文章內(nèi)容簡介】 FFFFFF，所以memset沒錯 memset(Order,1,sizeof(Order))。 memset(Part,1,sizeof(Part))。 for (int v=0。vMAXVERTEX。v++) if (Order[v]==1) Gabow(v)。 WCHAR Tmp[100]={0}。 WCHAR Result[200]={0}。 for (int i=1。iPartNum+1。i++) { wsprintf(Tmp,TEXT(第%d組強連通分量：),i)。 wcscat(Result,Tmp)。 for (int v=0。vMAXVERTEX。v++) { if (Part[v]==i) { wsprintf(Tmp,TEXT(%d ),v)。 wcscat(Result,Tmp)。 } } wcscat(Result,TEXT(\n))。 } MessageBox(NULL,Result,TEXT(Title),MB_OK)。 return 0。}vector型數(shù)組Edge表示圖的鄰接表形式。圖是這個樣子的：0 → 1 ↓↖ ↓ 2 → 3 ↓ ↓ 4 → 5 WinMain函數(shù)中的循環(huán)逐個檢查未被檢查過的頂點，調(diào)用Gabow函數(shù)。Gabow函數(shù)檢測一個頂點v，將頂點v標記，并分別放入棧Path和Root中。如果頂點v指向其它頂點，則對于每個指向的頂點next：如果next是沒有檢測過的頂點（Order[next]不為1），遞歸地調(diào)用Gabow函數(shù)，繼續(xù)進行深度優(yōu)先搜索檢測。如果next已經(jīng)檢測過，而且已經(jīng)確定它所屬的強連通分量（Part[next]!=1），說明對它的檢測已完成，且只能由v到next，不能由next到v。它現(xiàn)在不在棧中，忽略。如果next已經(jīng)檢測過，但沒有確定其所屬的強連通分量（Part[next]==1），說明現(xiàn)在發(fā)現(xiàn)了一個有向環(huán)。由next出發(fā)，到vi，到vj，到vk……到v，又到next。這些頂點都是強連通的。其中next是這個強連通分量的根，它最早進入Root棧，現(xiàn)在還在棧中。根據(jù)保存的頂點檢查次序，將Root棧中next之后進入的頂點全部刪除，僅保留根next。其實每一次將頂點放入Root，都可以理解為每個檢查到的頂點是一個單獨的強連通分量，根就是它自己。直到
語文相關推薦
鄂ICP備17016276號-1