delete [] bin;}

void InsertBins(int b, int v)

在箱子b中添加頂點v

void MoveBins(int bMax, int ToBin, int v)

從當前箱子中移動頂點v到箱子To B i n

int *bin;

b i n [ i ]指向代表該箱子的雙向鏈表的首節(jié)點

N o d e Type *node;

n o d e [ i ]代表存儲頂點i的節(jié)點

圖1-9 實現雙向鏈接箱子所需的U n d i r e c t e d私有成員

 

程序13-3 箱子函數的定義

void Undirected::CreateBins(int b, int n)

{// 創(chuàng)建b個空箱子和n個節(jié)點

node = new NodeType [n+1];

bin = new int [b+1];

// 將箱子置空

for (int i = 1; i <= b; i++)

bin[i] = 0;

}

void Undirected::InsertBins(int b, int v)

{// 若b不為０，則將v 插入箱子b

if (!b) return; // b為0，不插入

node[v].left = b; // 添加在左端

if (bin[b]) node[bin[b]].left = v;

node[v].right = bin[b];

bin[b] = v;

}

void Undirected::MoveBins(int bMax, int ToBin, int v)

{// 將頂點v 從其當前所在箱子移動到To B i n .

// v的左、右節(jié)點

int l = node[v].left;

int r = node[v].right;

// 從當前箱子中刪除

if (r) node[r].left = node[v].left;

if (l > bMax || bin[l] != v) // 不是最左節(jié)點

node[l].right = r;

else bin[l] = r; // 箱子l的最左邊

// 添加到箱子To B i n

I n s e r t B i n s ( ToBin, v);

}

函數C r e a t e B i n s動態(tài)分配兩個數組： n o d e和b i n，n o d e [i ]表示頂點i, bin[i ]指向其N e w值為i的雙向鏈表的頂點, f o r循環(huán)將所有雙向鏈表置為空。如果b≠0，函數InsertBins 將頂點v 插入箱子b 中。因為b 是頂點v 的New 值，b = 0意味著頂點v 不能覆蓋B中當前還未被覆蓋的任何頂點，所以，在建立覆蓋時這個箱子沒有用處，故可以將其舍去。當b≠0時，頂點n 加入New 值為b 的雙向鏈表箱子的最前面，這種加入方式需要將node[v] 加入bin[b] 中第一個節(jié)點的左邊。由于表的最左節(jié)點應指向它所屬的箱子，因此將它的node[v].left 置為b。若箱子不空，則當前第一個節(jié)點的left 指針被置為指向新節(jié)點。node[v] 的右指針被置為b i n [ b ]，其值可能為0或指向上一個首節(jié)點的指針。最后， b i n [ b ]被更新為指向表中新的第一個節(jié)點。MoveBins 將頂點v 從它在雙向鏈表中的當前位置移到New 值為ToBin 的位置上。其中存在bMa x，使得對所有的箱子b i n[ j ]都有：如j>bMa x，則b i n [ j ]為空。代碼首先確定n o d e [ v ]在當前雙向鏈表中的左右節(jié)點，接著從雙鏈表中取出n o d e [ v ]，并利用I n s e r t B i n s函數將其重新插入到b i n [ To B i n ]中。

4. Undirected::BipartiteCover的實現

函數的輸入參數L用于分配圖中的頂點（分配到集合A或B）。L [i ] = 1表示頂點i在集合A中，L[ i ] = 2則表示頂點在B中。函數有兩個輸出參數： C和m，m為所建立的覆蓋的大小， C [ 0 , m - 1 ]是A中形成覆蓋的頂點。若二分圖沒有覆蓋，函數返回f a l s e；否則返回t r u e。完整的代碼見程序1 3 - 4。

程序13-4 構造貪婪覆蓋

bool Undirected::BipartiteCover(int L[], int C[], int& m)

{// 尋找一個二分圖覆蓋

// L 是輸入頂點的標號, L[i] = 1 當且僅當i 在Ａ中

// 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覆蓋了Ｂ中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 ) ; }

}