id5.txt

介绍动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。

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 ]指向代表该箱子的双向链表的首节点

N o d e Type *node;

n o d e [ i ]代表存储顶点i的节点

图1-9 实现双向链接箱子所需的U n d i r e c t e d私有成员

 

程序13-3 箱子函数的定义

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

{// 创建b个空箱子和n个节点

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的左、右节点

int l = node[v].left;

int r = node[v].right;

// 从当前箱子中删除

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

if (l > bMax || bin[l] != v) // 不是最左节点

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动态分配两个数组： n o d e和b i n，n o d e [i ]表示顶点i, bin[i ]指向其N e w值为i的双向链表的顶点, f o r循环将所有双向链表置为空。如果b≠0，函数InsertBins 将顶点v 插入箱子b 中。因为b 是顶点v 的New 值，b = 0意味着顶点v 不能覆盖B中当前还未被覆盖的任何顶点，所以，在建立覆盖时这个箱子没有用处，故可以将其舍去。当b≠0时，顶点n 加入New 值为b 的双向链表箱子的最前面，这种加入方式需要将node[v] 加入bin[b] 中第一个节点的左边。由于表的最左节点应指向它所属的箱子，因此将它的node[v].left 置为b。若箱子不空，则当前第一个节点的left 指针被置为指向新节点。node[v] 的右指针被置为b i n [ b ]，其值可能为0或指向上一个首节点的指针。最后， b i n [ b ]被更新为指向表中新的第一个节点。MoveBins 将顶点v 从它在双向链表中的当前位置移到New 值为ToBin 的位置上。其中存在bMa x，使得对所有的箱子b i n[ j ]都有：如j>bMa x，则b i n [ j ]为空。代码首先确定n o d e [ v ]在当前双向链表中的左右节点，接着从双链表中取出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 ) ; }

}