二分圖是一個無向圖它的n 個頂點可二分為集合A和集合B且同一集合中的任意兩個頂點在圖中無邊相連(即任何一條邊都是一個頂點在集合A中另一個在集合B中)當且僅當B中的每個頂點至少與A中一個頂點相連時A的一個子集A 覆蓋集合B(或簡單地說A 是一個覆蓋)覆蓋A 的大小即為A 中的頂點數目當且僅當A 是覆蓋B的子集中最小的時A 為最小覆蓋
例 考察如圖 所示的具有 個頂點的二分圖A={ }和B={ }子集A = { }是B的最小覆蓋在二分圖中尋找最小覆蓋的問題為二分覆蓋( b i p a r t i t e c o v e r)問題在例 中說明了最小覆蓋是很有用的因為它能解決在會議中使用最少的翻譯人員進行翻譯這一類的問題
二分覆蓋問題類似於集合覆蓋( s e t c o v e r)問題在集合覆蓋問題中給出了k 個集合S= {S S Sk }每個集合Si 中的元素均是全集U中的成員當且僅當èi SSi =U時S的子集S 覆蓋US 中的集合數目即為覆蓋的大小當且僅當沒有能覆蓋U的更小的集合時稱S 為最小覆蓋可以將集合覆蓋問題轉化為二分覆蓋問題(反之亦然)即用A的頂點來表示S Sk B中的頂點代表U中的元素當且僅當S的相應集合中包含U中的對應元素時在A與B的頂點之間存在一條邊
例 令S= {S S } U= { } S = { }S = { }S = { }S = { }S = { }S = {SSS }是一個大小為的覆蓋沒有更小的覆蓋 S 即為最小覆蓋這個集合覆蓋問題可映射為圖的二分圖即用頂點 和 分別表示集合SSSS 和S頂點j 表示集合中的元素j≤j≤
集合覆蓋問題為N P復雜問題由於集合覆蓋與二分覆蓋是同一類問題二分覆蓋問題也是N P復雜問題因此可能無法找到一個快速的算法來解決它但是可以利用貪婪算法尋找一種快速啟發式方法一種可能是分步建立覆蓋A 每一步選擇A中的一個頂點加入覆蓋頂點的選擇利用貪婪准則從A中選取能覆蓋B中還未被覆蓋的元素數目最多的頂點
例 考察圖 所示的二分圖初始化A = 且B中沒有頂點被覆蓋頂點和 均能覆蓋B中的六個頂點頂點覆蓋五個頂點和 分別覆蓋四個因此在第一步往A 中加入頂點或 若加入頂點 則它覆蓋的頂點為{ }未覆蓋的頂點為{ }頂點能覆蓋其中四個頂點( { })頂點 覆蓋一個( { } )頂點覆蓋一個({ })頂點 覆蓋零個頂點 覆蓋四個{ }下一步可選擇或 加入A 若選擇頂點則頂點{ } 仍然未被覆蓋此時頂點 不覆蓋其中任意一個頂點覆蓋一個頂點 覆蓋兩個因此選擇頂點 至此所有頂點已被覆蓋得A = { }
圖 給出了貪婪覆蓋啟發式方法的偽代碼可以證明 ) 當且僅當初始的二分圖沒有覆蓋時算法找不到覆蓋;) 啟發式方法可能找不到二分圖的最小覆蓋
數據結構的選取及復雜性分析
為實現圖 的算法需要選擇A 的描述方法及考慮如何記錄A中節點所能覆蓋的B中未覆蓋節點的數目由於對集合A 僅使用加法運算則可用一維整型數組C來描述A 用m 來記錄A 中元素個數將A 中的成員記錄在C[ :m] 中對於A中頂點i令N e wi 為i 所能覆蓋的B中未覆蓋的頂點數目逐步選擇N e wi 值最大的頂點由於一些原來未被覆蓋的頂點現在被覆蓋了因此還要修改各N e wi 值在這種更新中檢查B中最近一次被V覆蓋的頂點令j 為這樣的一個頂點則A中所有覆蓋j 的頂點的N e wi 值均減
例 考察圖 初始時(N e w N e w N e w N e w N e w ) = ( )假設在例 中第一步選擇頂點 為更新N e wi 的值檢查B中所有最近被覆蓋的頂點這些頂點為 和 當檢查頂點時將頂點和 的N e wi 值分別減因為頂點不再是被頂點和 覆蓋的未覆蓋節點;當檢查頂點時頂點 和 的相應值分別減;同樣檢查頂點時和 的值分別減;當檢查完所有最近被覆蓋的頂點得到的N e wi 值為()下一步選擇頂點最新被覆蓋的頂點為和 ;檢查頂點時N e w N e w 和N e w 的值減;檢查頂點時N e w 的值減因為頂點是覆蓋的唯一頂點
為了實現頂點選取的過程需要知道N e wi 的值及已被覆蓋的頂點可利用一個二維數組來達到這個目的N e w是一個整型數組New[i] 即等於N e wi且c o v為一個布爾數組若頂點i未被覆蓋則c o v [ i ]等於f a l s e否則c o v [ i ]為t r u e現將圖 的偽代碼進行細化得到圖
m=; //當前覆蓋的大小
對於A中的所有iNew[i]=Degree[i]
對於B中的所有iC o v [ i ] = f a l s e
while (對於A中的某些iNew[i]>) {
設v是具有最大的N e w [ i ]的頂點;
C [ m + + ] = v ;
for ( 所有鄰接於v的頂點j) {
if (!Cov[j]) {
Cov[j]= true;
對於所有鄰接於j的頂點使其N e w [ k ]減
} } }
if (有些頂點未被覆蓋) 失敗
else 找到一個覆蓋
圖 圖的細化
更新N e w的時間為O (e)其中e 為二分圖中邊的數目若使用鄰接矩陣則需花(n ) 的時間來尋找圖中的邊若用鄰接鏈表則需(n+e) 的時間實際更新時間根據描述方法的不同為O (n ) 或O (n+e)逐步選擇頂點所需時間為(S i z e O f A)其中S i z e O f A=| A |因為A的所有頂點都有可能被選擇因此所需步驟數為O ( S i z e O f A )覆蓋算法總的復雜性為O ( S i z e O f A +n) = O ( n)或O (S i z e Of A+n + e)
降低復雜性
通過使用有序數組N e wi最大堆或最大選擇樹(max selection tree)可將每步選取頂點v的復雜性降為( )但利用有序數組在每步的最後需對N e wi 值進行重新排序若使用箱子排序則這種排序所需時間為(S i z e O f B ) ( S i z e O fB =|B| ) (見 節箱子排序)由於一般S i z e O f B比S i z e O f A大得多因此有序數組並不總能提高性能
如果利用最大堆則每一步都需要重建堆來記錄N e w值的變化可以在每次N e w值減時進行重建這種減法操作可引起被減的N e w值最多在堆中向下移一層因此這種重建對於每次N e w值減需( )的時間總共的減操作數目為O (e)因此在算法的所有步驟中維持最大堆僅需O (e)的時間因而利用最大堆時覆蓋算法的總復雜性為O (n )或O (n+e)
若利用最大選擇樹每次更新N e w值時需要重建選擇樹所需時間為(log S i z e O f A)重建的最好時機是在每步結束時而不是在每次N e w值減時需要重建的次數為O (e)因此總的重建時間為O (e log S i z e OfA)這個時間比最大堆的重建時間長一些然而通過維持具有相同N e w值的頂點箱子也可獲得和利用最大堆時相同的時間限制由於N e w的取值范圍為到S i z e O f B需要S i z e O f B+ 個箱子箱子i 是一個雙向鏈表鏈接所有N e w值為i 的頂點在某一步結束時假如N e w [ ]從 變到則需要將它從第 個箱子移到第個箱子利用模擬指針及一個節點數組n o d e(其中n o d e [ i ]代表頂點in o d e [ i ] l e f t和n o d e [ i ] r i g h t為雙向鏈表指針)可將頂點從第 個箱子移到第個箱子從第 個箱子中刪除n o d e [ ]並將其插入第個箱子利用這種箱子模式可得覆蓋啟發式算法的復雜性為O (n )或O(n+e)(取決於利用鄰接矩陣還是線性表來描述圖)
雙向鏈接箱子的實現
為了實現上述雙向鏈接箱子圖 定義了類U n d i r e c t e d的私有成員N o d e Ty p e是一個具有私有整型成員l e f t和r i g h t的類它的數據類型是雙向鏈表節點程序 給出了U n d i r e c t e d的私有成員的代碼
void CreateBins (int b int n)
創建b個空箱子和n個節點
void DestroyBins() { delete [] node;
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的節點
圖 實現雙向鏈接箱子所需的U n d i r e c t e d私有成員
程序 箱子函數的定義
void Undirected::CreateBins(int b int n)
{// 創建b個空箱子和n個節點
node = new NodeType [n+];
bin = new int [b+];
// 將箱子置空
for (int i = ; i <= b; i++)
bin[i] = ;
}
void Undirected::InsertBins(int b int v)
{// 若b不為則將v 插入箱子b
if (!b) return; // b為不插入
node[v]left = b; // 添加在左端
if (bin[b]) node[bin[b]]left = v;
node[v]right = bin[b];
bin[b]
From:http://tw.wingwit.com/Article/program/sjjg/201311/23593.html
