二分圖與最小生成樹

最小生成樹

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

最小生成樹演算法 :

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 ;
}