首先計算出集合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 wk = 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);}
二分圖
17個頂點的二分圖