二分圖與最小生成樹

2020-10-16 14:00:23

最小生成樹

最小生成樹對應的問題都是無向圖

最小生成樹演演算法 :

  1. Prim演演算法
    1. 稠密圖 : 樸素版Prim演演算法 O( n^2 ) [^程式碼短 一般用於稠密圖]
    2. 稀疏圖 : 堆優化版Prim演演算法 O( mlog(n) ) [^不常用]
  2. Kruskal演演算法 O( mlog(m) ) [^一般用於稀疏圖]

捋清演演算法思路 , 弄清楚演演算法的流程 , 不是死記模版

樸素版Prim演演算法

集合 s 表示當前已經在連通塊中的點

步驟 :

  1. 將所有距離初始化為正無窮 . dist[i] --> INF
  2. 進行 n 次迭代 , for(int i = 0;i < n;i ++ )
    1. 找到 不在集合 s 中的距離最小的點
    2. 用 t 更新其他點到 集合(與Dijkstra演演算法的區別處) 的距離
    3. 將 t 加入到集合當中 st[t] = true

模版 :

給定一個n個點m條邊的無向圖 , 圖中可能存在重邊和自環 , 邊權可能為負數.

求最小生成樹的樹邊權重之和 , 如果最小生成樹不存在則輸出 impossible.

1 <= n <= 500 , 1 <= m <= 10^5

輸入樣例 :

4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4

輸出樣例 :

6

點到集合的距離 : 點到集合中的點的所有邊中最短的那條邊

最小生成樹中, 沒有環 , 因此正邊和負邊都可以

程式碼如下 :

// 樸素版 Prim演演算法 :

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std ;
const int N = 510 , INF = 0x3f3f3f3f ;
int dist[N] ; bool st[N] ; int n , m ; int g[N][N] ; // 稠密圖 , 鄰接矩陣儲存

int prim()
{
    memset(dist,0x3f,sizeof dist) ; // 初始狀態 , 所有點到集合的距離均為無窮大

    int res = 0 ; // res 記錄最小生成樹的各邊的權值的和
    // n 個點 , 迭代 n 次
    for(int i = 0;i < n;i ++ )
    {
        int t = -1 ;
        // 從集合外的點集中找到距離當前集合距離最短的點 , 第一次時隨機選擇
        for(int j = 1;j <= n;j ++ )
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j ;
            }
        }

        if(i && dist[t] == INF) return -1 ; // 如果當前不是第一個點且其到集合的距離為INF,則該圖不連通
        if(i) res += dist[t] ;
        // 注意 : 這裡可能存在自環的情況 , 所以應該先累加邊的權值 , 再進行更新
        for(int j = 1;j <= n;j ++ ) dist[j] = min(dist[j] , g[t][j]) ; // 更新集合外的點到集合的距離

        st[t] = true ; // 將點 t 加入到集合當中
    }
    return res ;
}

int main()
{
    scanf("%d%d",&n,&m) ;

    memset(g,0x3f,sizeof g) ;

    while (m -- )
    {
        int a , b , c ; scanf("%d%d%d",&a,&b,&c) ;
        g[a][b] = g[b][a] = min(g[a][b] , c) ; // 存在重邊 , 取最小值
    }

    int t = prim() ;

    if(t == -1) puts("impossible") ;
    else printf("%d \n",t) ;

    return 0 ;
} 

Kruskal演演算法

步驟 :

  1. 將所有邊按權重從小到大排序( sort ) 時間複雜度 : O( mlogm ) e
  2. 列舉每條邊 a --> b , 權重為 c .
    1. 如果 a , b 不連通 , 將這條邊加入到集合中 ( 並查集的簡單應用 )

模版 :

給定一個n個點m條邊的無向圖 , 圖中可能存在重邊和自環 , 邊權可能為負數.

求最小生成樹的樹邊權重之和 , 如果最小生成樹不存在則輸出 impossible.

不需存圖 , 直接開一個結構體存邊即可

輸入樣例 :

4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4

輸出樣例 :

6

程式碼如下 :

// Kruskal 演演算法 :

#include <iostream>
#include <algorithm>

using namespace std ;
const int N = 100010 ;
int n , m ; int p[N] ;

struct Edge{
    int a , b , w ;
    bool operator< (const Edge & W) const // 過載小於號 , 使排序的時候按w的值排序
    {
        return w < W.w ;
    }
}edges[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]) ;
    return p[x] ;
}

int main()
{
    scanf("%d%d",&n,&m) ;

    for(int i = 0;i < m;i ++ )
    {
        int a , b , w ; scanf("%d%d%d",&a,&b,&w) ;
        edges[i] = {a , b , w} ;
    }

    sort(edges , edges + m) ;

    for(int i = 1;i <= n;i ++ ) p[i] = i ; // 初始化並查集陣列

    int res = 0 , cnt = 0 ;
    for(int i = 0;i < m;i ++ )
    {
        int a = edges[i].a , b = edges[i].b , w = edges[i].w ;
        a = find(a) , b = find(b) ;

        if(a != b)
        {
            p[a] = b ;
            res += w ;
            cnt ++ ;
        }
    }

    if( cnt != n - 1 ) puts("impossible") ;
    else printf("%d \n",res) ;

    return 0 ;
}

二分圖

簡介 : 二分圖,又稱二部圖,英文名叫 Bipartite graph。

節點由兩個集合組成,且兩個集合內部沒有邊的圖。

換言之,存在一種方案,將節點劃分成滿足以上性質的兩個集合。

*性質 : 二分圖不存在長度為奇數的環 充分必要

因為每一條邊都是從一個集合走到另一個集合,只有走偶數次才可能回到同一個集合。

染色法

時間複雜度 : O ( n + m ) 線性 . 類似於dfs

如果在染色過程中出現矛盾 --> 存在奇數環 , 不是二分圖

反之 , 則是二分圖

模版 : 染色法判定二分圖 :

給定一個n個點m條邊的無向圖 ,圖中可能存在重邊或自環,判斷這個圖是否是二分圖

輸入樣例 :

4 4

1 3

1 4

2 3

2 4

輸出樣例 :

Yes

程式碼如下 :

// 二分圖的染色法 : 

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std ; 
const int N = 100010 , M = N << 1 ; 
int h[N] , e[M] , ne[M] , idx ; int color[N] ; 
int n , m ; 

void add(int a,int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ; 
}

bool dfs(int u,int c)
{
    color[u] = c ; // 給 u 點染色
    for(int i = h[u] ; i != -1;i = ne[i])
    {
        int j = e[i] ; 
        if (!color[j])
        {
            if(!dfs(j,3 - c)) // 因為 j 是u 的相鄰點 , 所以給其染色時要與u不一樣 , 3-u即可
            {
                return false ; 
            }
        }
        else if (color[j] == c) return false ; // 如果 j 的顏色與 u相同,不行,因為它們是相鄰點
    }
    return true ; 
}

int main()
{
    scanf("%d%d",&n,&m) ; 
    
    memset(h,-1,sizeof h) ; 
    
    while (m -- )
    {
        int a , b ; scanf("%d%d",&a,&b) ; 
        add(a,b) ; add(b,a) ; 
    }
    
    bool flag = true ; 
    for(int i = 1;i <= n;i ++ )
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag = false ; break ; 
            }
        }
    }
    
    if(!flag) puts("No") ; 
    else puts("Yes") ; 
    
    return 0 ; 
}

匈牙利演演算法

時間複雜度 : O ( mn ) , 實際執行時間一般遠小於 O( mn )

匹配:在圖論中,一個「匹配」(matching)是一個邊的集合,其中任意兩條邊都沒有公共頂點。

交替路:從一個未匹配點出發,依次經過非匹配邊、匹配邊、非匹配邊…形成的路徑叫交替路。

增廣路:從一個未匹配點出發,走交替路,如果途徑另一個未匹配點(出發的點不算),則這條交替路稱為增廣路(agumenting path)。

增廣路有一個重要特點:非匹配邊比匹配邊多一條。因此,研究增廣路的意義是改進匹配。只要把增廣路中的匹配邊和非匹配邊的身份交換即可。由於中間的匹配節點不存在其他相連的匹配邊,所以這樣做不會破壞匹配的性質。

我們可以通過不停地找增廣路來增加匹配中的匹配邊和匹配點。找不到增廣路時,達到最大匹配(這是增廣路定理)。匈牙利演演算法正是這麼做的。

匈牙利樹一般由 BFS 構造(類似於 BFS 樹)。從一個未匹配點出發執行 BFS(唯一的限制是,必須走交替路),直到不能再擴充套件為止。

匈牙利樹要求所有葉子節點均為匹配點.

匈牙利演演算法 : 求解一個圖中的最大匹配

匈牙利演演算法的要點如下

  1. 從左邊第 1 個頂點開始,挑選未匹配點進行搜尋,尋找增廣路。
    1. 如果經過一個未匹配點,說明尋找成功。更新路徑資訊,匹配邊數 +1,停止搜尋。
    2. 如果一直沒有找到增廣路,則不再從這個點開始搜尋。事實上,此時搜尋後會形成一棵匈牙利樹。我們可以永久性地把它從圖中刪去,而不影響結果。
  2. 由於找到增廣路之後需要沿著路徑更新匹配,所以我們需要一個結構來記錄路徑上的點。DFS 版本通過函數呼叫隱式地使用一個棧,而 BFS 版本使用 prev 陣列。

效能比較

兩個版本的時間複雜度均為O(V⋅E)O(V⋅E)。DFS 的優點是思路清晰、程式碼量少,但是效能不如 BFS。我測試了兩種演演算法的效能。對於稀疏圖,BFS 版本明顯快於 DFS 版本;而對於稠密圖兩者則不相上下。在完全亂資料 9000 個頂點 4,0000 條邊時前者領先後者大約 97.6%,9000 個頂點 100,0000 條邊時前者領先後者 8.6%, 而達到 500,0000 條邊時 BFS 僅領先 0.85%。

補充定義和定理:

最大匹配數:最大匹配的匹配邊的數目

最小點覆蓋數:選取最少的點,使任意一條邊至少有一個端點被選擇

最大獨立數:選取最多的點,使任意所選兩點均不相連

最小路徑覆蓋數:對於一個 DAG(有向無環圖),選取最少條路徑,使得每個頂點屬於且僅屬於一條路徑。路徑長可以為 0(即單個點)。

定理1:最大匹配數 = 最小點覆蓋數(這是 Konig 定理)

定理2:最大匹配數 = 最大獨立數

定理3:最小路徑覆蓋數 = 頂點數 - 最大匹配數

​ 選自 : https://www.renfei.org/blog/bipartite-matching.html

模版 :

給定一個二分圖 , 其中左半部包含 n1 個點 ( 編號1~n1 ) , 右半部分包含 n2 個點 (編號 1 ~ n2) , 二分圖共包含 m 條邊. 求出二分圖的最大匹配數.

輸入樣例 :

2 2 4

1 1

1 2

2 1

2 2

輸出樣例 :

2

程式碼如下 :

// Huagarian 匈牙利演演算法 :

// hungarian(匈牙利演演算法) :

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std ;
const int N = 510 , M = 100010 ;
int n1 , n2 , m ;
int h[N] , e[M] , ne[M] , idx ;
int match[N] ; // 右邊的點所對應的左邊的點
bool st[N] ; // 判重 , 保證每個點只匹配一個點 , 否則會無限迴圈

void add(int a,int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}

// 寫迭代遞迴類演演算法時 , 相信其能完成我們給定的功能 , 不用去繞進去想
bool find(int x)
{
    for(int i = h[x];i != -1;i = ne[i])
    {
        int j = e[i] ;
        if(!st[j])
        {
            st[j] = true ; 
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x ;
                return true ;
            }
        }
    }
    return false ;
}

int main()
{
    scanf("%d%d%d",&n1,&n2,&m) ;
    
    memset(h,-1,sizeof h) ;

    while (m -- )
    {
        int a , b ; scanf("%d%d",&a,&b) ; add(a , b) ;
    }


    int res = 0 ;
    for(int i = 1;i <= n1;i ++ )
    {
        memset(st,false,sizeof st) ; // 清空 , 表示右邊的點都還沒考慮過 
        if(find(i)) res ++ ;
    }

    printf("%d\n",res) ;

    return 0 ;
}