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