二分图判别算法

下面的表述主要以严谨的图论表述为主：

将阐述以下三点：

• 二分图的定义
• 标记法判别连通图
• 染色法-二分图判别算法（使用深度优先算法 DFS）

一、二分图定义

二分图是图论中的一种特殊模型：

若能将无向图 G=(V,E) 的顶点 V 划分为两个交集为空的顶点集，并且任意边的两个端点都分属于两个集合，则称图 G 为一个为二分图

也就是说：它可以被划分为两个部分，每个部分内的点​互不相连。

​​

二、标记法判别连通图

这里补充一个连通图的判别方法，或者说是判断一个图 G=(V,E)能够划分为连通图的最少数量

• 给定一个有 V 个顶点的图(邻接矩阵）
• int k=1
• A 操作={任取一个点标记为 k，将所有与标记 k 相连的点都标记为 k，直到检查到与 k 相连的点都标记为 k，记录已经标记的点总数 X}
• if（X==V） return k
• else k=k+1 重复 A 操作

def dfs(graph, visited, v):  
    visited[v] = True  
    count = 1  # 计数当前连通分量的点数  
    for i in range(len(graph)):  
        if graph[v][i] == 1 and not visited[i]:  
            count += dfs(graph, visited, i)  # 递归DFS，计数  
    return count  
def find_k(graph):  
    V = len(graph)  
    k = 1  
    while k <= V: 
        visited = [False] * V 
        total_count = 0  
        for v in range(V):  # 遍历每个顶点  
            if not visited[v]:  
                count = dfs(graph, visited, v)  # 深度优先遍历，计数  
                total_count += count  
        if total_count == V: 
            return k 
        k += 1   
# 示例  
graph = [  
    [0, 1, 0, 0],  
    [1, 0, 1, 1],  
    [0, 1, 0, 0],  
    [0, 1, 0, 0]  
]  
result = find_k(graph)  
print(result) 
​

判别连通图的方法下面判别二分图需要用到

三、染色法判别二分图

我们想象二分图也就是把一个图划分，划分内部不相连，也就是我们可以把相连表示仇视关系，利用敌人的敌人是朋友的思想，我就产生了递归染色法的想法：

• 设置一个起始点染色为红色，相连的均染为蓝色，连接蓝色的点检查是否染色，如果没有染色则染为红色，以此遍历整个**连通图，​直到染色点数==连通图点数 V_i
• 我们注意到这只能在连通图内进行，所以我们才要用上面引出连通图的算法，所以我们应该在第 1 块、第 2 块……第 k 块都设置一个起始点，这样就可以保证染色到整个图
• 最后，我们检查每一条边是否出现连接的点是同色，如果存在则该图不是二分图，反之成立

Code-hxw

def dfs_connected(graph, visited, v):  
    visited[v] = True  
    for i in range(len(graph)):  
        if graph[v][i] == 1 and not visited[i]:  # 如果有边且未访问  
            dfs_connected(graph, visited, i)  
def count_connected_components(graph):  
    V = len(graph)  
    visited = [False] * V  
    count = 0  
    for v in range(V):  
        if not visited[v]:  # 若未访问，意味着找到一个新连通分量  
            dfs_connected(graph, visited, v)  
            count += 1  
    return count  
def is_bipartite_with_groups(graph):  
    V = len(graph)  
    color = [-1] * V  # -1 表示未染色  
    groups = {0: [], 1: []}  # 用于存储两个组的顶点  
    def dfs_bipartite(v, c):  
        color[v] = c  
        groups[c].append(v)  # 将顶点添加到相应的组  
        for i in range(V):  
            if graph[v][i] == 1:  # 检查相连的边  
                if color[i] == -1:  # 若未染色  
                    if not dfs_bipartite(i, 1 - c):  # 递归染色（反色）  
                        return False  
                elif color[i] == c:  
                    return False  
        return True  
    for start in range(V):  
        if color[start] == -1:  # 若未染色，开始染色  
            groups = {0: [], 1: []}  
            if not dfs_bipartite(start, 0):  
                return False, {}  
    return True, groups  
# 示例邻接矩阵  
graph = [  
    [0, 1, 0, 0, 1],  
    [1, 0, 1, 0, 0],  
    [0, 1, 0, 1, 0],  
    [0, 0, 1, 0, 1],  
    [1, 0, 0, 1, 0]  
] 
connected_components = count_connected_components(graph)  
print(f"Connected components: {connected_components}")  
is_bipartite_graph, bipartite_groups = is_bipartite_with_groups(graph)  
if is_bipartite_graph:  
    print("True")  
    print(f"Bipartite groups: {bipartite_groups[0]} and {bipartite_groups[1]}")  
else:  
    print("False")
​

‍

‍