数据结构-贪心算法.ppt

伪代码细化 m=0;//当前覆盖的大小 对于A中的所有i，New[i]=Degree[i] 对于B中的所有i，Cov[i]=false while (对于A中的某些i,New[i]0){ 设v是具有最大的New[i]的顶点； C[m++]=v; for(所有邻接于v的顶点j){ if(!Cov[j]){ Cov[j]=true; 对于所有邻接于j的顶点，使其New[k]减1 }}} if (有些顶点未被覆盖)失败 else 找到一个覆盖 邻接矩阵：O(n2) 邻接链表：O(|A|2＋n+e) 优化 顶点v的选择?Q(1) 有序数组 修正New后需重新排序，Q(|B|)，未必小于Q(|A|2) 最大堆 修正New后重建堆，New值减1，最多下降一层，O(e)?O(n2)和O(n+e) 最大选择树：O(elog|A|) 维护具有相同New值的顶点箱子 |B|+1个箱子，箱子i——New值为i的顶点形成的双向链表，与最大堆性能相同 双向链接箱子的实现 void Undirected::CreateBins(int b, int n) {// Create b empty bins and n nodes. node = new NodeType [n+1]; bin = new int [b+1]; // set bins empty for (int i = 1; i = b; i++) bin[i] = 0; } 插入箱子 void Undirected::InsertBins(int b, int v) {// Insert v into bin b unless b is zero. if (!b) return; // do not insert in bin 0 node[v].left = b; // add at left end 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) {// Move vertex v from its current bin to bin ToBin. // nodes to the left and right of v int l = node[v].left; int r = node[v].right; // delete from current bin if (r) node[r].left = node[v].left; if (l bMax || bin[l] != v) // not left-most one node[l].right = r; else bin[l] = r; // left-most in bin l // add to bin ToBin InsertBins(ToBin, v); } 覆盖算法实现 bool Undirected::BipartiteCover(int L[], int C[], int m) {// Find a cover of the bipartite graph. // L is the input vertex labeling, L[i] = 1 iff i is // in A. C is an output array that identifies the // cover. Return false if the graph has no cover. // If the graph has a cover, return true; // return cover size in m; and cover in C[0:m-1]. int n = Vertices(); // create structures 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]; // vertex i covers New[i] uncove