首先計算出集合A和B的大小、初始化必要的雙向鍊表結構、創建三個數組、初始化圖遍歷器、並創建一個棧。然後將數組C o v和C h a n g e初始化為f a l s e，並將A中的頂點根據它們覆蓋B中頂點的數目插入到相應的雙向鍊表中。
為了構造覆蓋，首先按SizeOfB遞減至1的順序檢查雙向鍊表。當發現一個非空的表時，就將其第一個頂點v加入到覆蓋中，這種策略即為選擇具有最大New值的頂點。將所選擇的頂點加入覆蓋數組C並檢查B中所有與它鄰接的頂點。若頂點j與v鄰接且還未被覆蓋，則將C o v [ j ]置為t r u e，表示頂點j現在已被覆蓋，同時將已被覆蓋的B中的頂點數目加1。由於j是最近被覆蓋的，所有A中與j鄰接的頂點的New值減1。下一個while循環降低這些New值並將New值被降低的頂點保存在一個棧中。當所有與頂點v鄰接的頂點的Cov值更新完畢後，New值反映了A中每個頂點所能覆蓋的新的頂點數，然而A中的頂點由於New值被更新，處於錯誤的雙向鍊表中，下一個while循環則將這些頂點移到正確的表中。
構造貪婪覆蓋
bool Undirected::BipartiteCover(int L[], int C[], int& m) {// 尋找一個二分圖覆蓋 // L 是輸入頂點的標號, L[i] = 1 若且唯若i 在A中 // C 是一個記錄覆蓋的輸出數組 // 如果圖中不存在覆蓋，則返回f a l s e // 如果圖中有一個覆蓋，則返回t r u e ; // 在m中返回覆蓋的大小; 在C [ 0 : m - 1 ]中返回覆蓋 int n = Ve r t i c e s ( ) ; // 外掛程式結構 int SizeOfA = 0; for (int i = 1; i <= n; i++) // 確定集合A的大小 if (L[i] == 1) SizeOfA++; int SizeOfB = n - SizeOfA; CreateBins(SizeOfB, n); int *New = new int [n+1]; / /頂點i覆蓋了B中N e w [ i ]個未被覆蓋的頂點 bool *Change = new bool [n+1]; // Change[i]為t r u e若且唯若New[i]已改變 bool *Cov = new bool [n+1]; // Cov[i] 為true 若且唯若頂點i 被覆蓋 I n i t i a l i z e P o s ( ) ; LinkedStack<int> S; // 初始化 for (i = 1; i <= n; i++) { Cov[i] = Change[i] = false; if (L[i] == 1) {// i 在A中 New[i] = Degree(i); // i 覆蓋了這么多 InsertBins(New[i], i);}} // 構造覆蓋 int covered = 0, // 被覆蓋的頂點 MaxBin = SizeOfB; // 可能非空的最大箱子 m = 0; // C的游標 while (MaxBin > 0) { // 搜尋所有箱子 // 選擇一個頂點 if (bin[MaxBin]) { // 箱子不空 int v = bin[MaxBin]; // 第一個頂點 C[m++] = v; // 把v 加入覆蓋 // 標記新覆蓋的頂點 int j = Begin(v), k; while (j) { if (!Cov[j]) {// j尚未被覆蓋 Cov[j] = true; c o v e r e d + + ; // 修改N e w k = Begin(j); while (k) { New[k]--; // j 不計入在內 if (!Change[k]) { S.Add(k); // 僅入棧一次 Change[k] = true;} k = NextVe r t e x ( j ) ; } } j = NextVe r t e x ( v ) ; } // 更新箱子 while (!S.IsEmpty()) { S . D e l e t e ( k ) ; Change[k] = false; MoveBins(SizeOfB, New[k], k);} } else MaxBin--; } D e a c t i v a t e P o s ( ) ; D e s t r o y B i n s ( ) ; delete [] New; delete [] Change; delete [] Cov; return (covered == SizeOfB); }
