Python案例如何用Scikit-learn做图着色

本文目录导读：

1. 方法1：使用贪心算法实现图着色
2. 方法2：使用DSATUR算法（更优化的着色）
3. 方法3：使用Scikit-learn进行聚类辅助着色
4. 实际应用示例：地图着色

我将为您展示如何使用Scikit-learn来实现图着色问题，图着色是一种将颜色分配给图节点的问题，要求相邻节点具有不同颜色。

方法1：使用贪心算法实现图着色

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from sklearn.preprocessing import LabelEncoder
from collections import defaultdict
def greedy_graph_coloring(edges, num_nodes):
    """
    使用贪心算法进行图着色
    """
    # 创建邻接表
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # 初始化颜色分配
    color_assignment = {}
    # 按度数降序访问节点
    nodes = sorted(range(num_nodes), key=lambda x: len(graph[x]), reverse=True)
    for node in nodes:
        # 找到邻居使用的颜色
        neighbor_colors = set()
        for neighbor in graph[node]:
            if neighbor in color_assignment:
                neighbor_colors.add(color_assignment[neighbor])
        # 选择最小的未使用颜色
        color = 0
        while color in neighbor_colors:
            color += 1
        color_assignment[node] = color
    return color_assignment
def visualize_coloring(edges, num_nodes, colors):
    """
    可视化图着色结果
    """
    # 创建图
    G = nx.Graph()
    G.add_nodes_from(range(num_nodes))
    G.add_edges_from(edges)
    # 获取颜色列表
    color_list = [colors[node] for node in range(num_nodes)]
    # 绘制图
    pos = nx.spring_layout(G, seed=42)
    nx.draw(G, pos, 
            node_color=color_list, 
            with_labels=True, 
            cmap=plt.cm.rainbow,
            node_size=500)
    plt.title(f"图着色结果 - 使用了 {len(set(color_list))} 种颜色")
    plt.show()
# 示例：创建一个简单图
def create_sample_graph():
    """创建示例图"""
    edges = [
        (0, 1), (0, 2), (0, 3),
        (1, 2), (1, 4),
        (2, 3), (2, 4),
        (3, 4),
        (5, 6), (6, 7), (7, 5)
    ]
    num_nodes = 8
    return edges, num_nodes
# 运行示例
if __name__ == "__main__":
    edges, num_nodes = create_sample_graph()
    colors = greedy_graph_coloring(edges, num_nodes)
    print("图着色结果：")
    for node, color in sorted(colors.items()):
        print(f"节点 {node} -> 颜色 {color}")
    print(f"\n总共使用了 {len(set(colors.values()))} 种颜色")
    visualize_coloring(edges, num_nodes, colors)

方法2：使用DSATUR算法（更优化的着色）

import networkx as nx
import matplotlib.pyplot as plt
from collections import defaultdict
class DSATURColoring:
    """
    DSATUR (Degree of Saturation) 算法的图着色实现
    """
    def __init__(self, edges, num_nodes):
        self.graph = defaultdict(list)
        for u, v in edges:
            self.graph[u].append(v)
            self.graph[v].append(u)
        self.num_nodes = num_nodes
        self.colors = {}
        self.saturation = defaultdict(int)  # 饱和度：已使用的不同颜色数
        self.available_colors = defaultdict(set)
    def get_saturation(self, node):
        """获取节点的饱和度"""
        return len(set(self.colors.get(n, -1) for n in self.graph[node] 
                      if n in self.colors))
    def get_degree(self, node):
        """获取节点的度数"""
        return len(self.graph[node])
    def color_graph(self):
        """执行DSATUR着色"""
        # 初始化所有节点为未着色
        uncolored = set(range(self.num_nodes))
        while uncolored:
            # 选择饱和度最高的节点（如果平局，选择度数高的）
            node = max(uncolored, key=lambda x: (self.get_saturation(x), 
                                                self.get_degree(x)))
            # 找到邻居使用的颜色
            neighbor_colors = set()
            for neighbor in self.graph[node]:
                if neighbor in self.colors:
                    neighbor_colors.add(self.colors[neighbor])
            # 选择最小的可用颜色
            color = 0
            while color in neighbor_colors:
                color += 1
            self.colors[node] = color
            # 更新饱和度
            for neighbor in self.graph[node]:
                if neighbor not in self.colors:
                    new_saturation = len(set(self.colors.get(n, -1) 
                                        for n in self.graph[neighbor] 
                                        if n in self.colors))
                    self.saturation[neighbor] = new_saturation
            uncolored.remove(node)
        return self.colors
# 测试DSATUR算法
def test_dsatur():
    """测试DSATUR算法"""
    # 创建一个更复杂的地图着色问题
    edges = [
        (0, 1), (0, 2),
        (1, 2), (1, 3), (1, 4),
        (2, 3), (2, 5),
        (3, 4), (3, 5), (3, 6),
        (4, 6),
        (5, 6),
        (7, 8), (8, 9), (9, 7),  # 另一个组件
        (7, 10), (8, 10)
    ]
    num_nodes = 11
    # 执行着色
    dsatur = DSATURColoring(edges, num_nodes)
    colors = dsatur.color_graph()
    print("DSATUR算法着色结果：")
    for node, color in sorted(colors.items()):
        print(f"节点 {node} -> 颜色 {color}")
    print(f"\n总共使用了 {len(set(colors.values()))} 种颜色")
    # 可视化
    G = nx.Graph()
    G.add_nodes_from(range(num_nodes))
    G.add_edges_from(edges)
    plt.figure(figsize=(10, 8))
    pos = nx.spring_layout(G, seed=42)
    color_list = [colors[node] for node in range(num_nodes)]
    nx.draw(G, pos, 
            node_color=color_list, 
            with_labels=True, 
            cmap=plt.cm.Set3,
            node_size=500,
            font_weight='bold')
    plt.title("DSATUR算法图着色结果")
    plt.show()
    # 验证着色是否正确
    verify_coloring(edges, colors)
def verify_coloring(edges, colors):
    """验证着色是否正确（相邻节点颜色不同）"""
    correct = True
    for u, v in edges:
        if colors[u] == colors[v]:
            print(f"错误：节点 {u} 和 {v} 颜色相同！")
            correct = False
    if correct:
        print("✓ 着色验证通过：所有相邻节点颜色都不同")
    else:
        print("✗ 着色验证失败")
if __name__ == "__main__":
    test_dsatur()

方法3：使用Scikit-learn进行聚类辅助着色

import networkx as nx
import matplotlib.pyplot as plt
from sklearn.cluster import SpectralClustering
from sklearn.neighbors import NearestNeighbors
import numpy as np
class SKLearnGraphColoring:
    """
    使用Scikit-learn进行基于聚类的图着色
    """
    def __init__(self, n_colors=3):
        self.n_colors = n_colors
        self.spectral = SpectralClustering(n_clusters=n_colors, 
                                          affinity='precomputed')
    def adjacency_to_similarity(self, edges, num_nodes):
        """将邻接矩阵转换为相似度矩阵"""
        similarity = np.eye(num_nodes)  # 对角线为1
        for u, v in edges:
            similarity[u][v] = 1
            similarity[v][u] = 1
        return similarity
    def color_graph(self, edges, num_nodes):
        """使用谱聚类进行着色"""
        similarity = self.adjacency_to_similarity(edges, num_nodes)
        # 执行谱聚类
        labels = self.spectral.fit_predict(similarity)
        # 调整颜色分配，确保相邻节点颜色不同
        colors = {}
        for i in range(num_nodes):
            colors[i] = labels[i]
        # 检测相邻节点的颜色冲突并解决
        colors = self.resolve_conflicts(edges, colors)
        return colors
    def resolve_conflicts(self, edges, colors):
        """解决相邻节点的颜色冲突"""
        max_attempts = 100
        attempt = 0
        resolved = False
        while not resolved and attempt < max_attempts:
            resolved = True
            for u, v in edges:
                if colors[u] == colors[v]:
                    # 找到新的颜色
                    available_colors = set(range(self.n_colors))
                    for neighbor in self.get_neighbors(edges, u):
                        if neighbor in colors:
                            available_colors.discard(colors[neighbor])
                    if available_colors:
                        colors[u] = min(available_colors)
                    else:
                        # 扩展颜色
                        colors[u] = max(colors.values()) + 1
                    resolved = False
            attempt += 1
        return colors
    def get_neighbors(self, edges, node):
        """获取节点的邻居"""
        neighbors = []
        for u, v in edges:
            if u == node:
                neighbors.append(v)
            elif v == node:
                neighbors.append(u)
        return neighbors
# 测试Scikit-learn方法
def test_sklearn_coloring():
    """测试基于Scikit-learn的图着色"""
    edges = [
        (0, 1), (0, 2), (0, 3),
        (1, 2), (1, 4),
        (2, 3), (2, 4),
        (3, 4),
        (5, 6), (6, 7), (7, 5)
    ]
    num_nodes = 8
    # 尝试不同的颜色数量
    for n_colors in [3, 4, 5]:
        print(f"\n尝试使用 {n_colors} 种颜色:")
        coloring = SKLearnGraphColoring(n_colors=n_colors)
        colors = coloring.color_graph(edges, num_nodes)
        # 验证
        valid = True
        for u, v in edges:
            if colors[u] == colors[v]:
                valid = False
                break
        if valid:
            print(f"✓ 成功使用 {n_colors} 种颜色完成着色")
            print(f"颜色分配: {colors}")
            # 可视化
            G = nx.Graph()
            G.add_nodes_from(range(num_nodes))
            G.add_edges_from(edges)
            plt.figure(figsize=(8, 6))
            pos = nx.spring_layout(G, seed=42)
            color_list = [colors[node] for node in range(num_nodes)]
            nx.draw(G, pos, 
                   node_color=color_list, 
                   with_labels=True, 
                   cmap=plt.cm.Set2,
                   node_size=500)
            plt.title(f"Scikit-learn谱聚类着色 ({n_colors}种颜色)")
            plt.show()
            break
        else:
            print(f"✗ 使用 {n_colors} 种颜色不够")
if __name__ == "__main__":
    test_sklearn_coloring()

实际应用示例：地图着色

import networkx as nx
import matplotlib.pyplot as plt
def create_map_coloring_problem():
    """创建地图着色问题（美国西部各州相邻关系）"""
    states = {
        'WA': ['OR', 'ID'],
        'OR': ['WA', 'ID', 'CA', 'NV'],
        'CA': ['OR', 'NV', 'AZ'],
        'ID': ['WA', 'OR', 'MT', 'WY', 'UT', 'NV'],
        'NV': ['OR', 'CA', 'ID', 'UT', 'AZ'],
        'UT': ['ID', 'NV', 'AZ', 'CO', 'WY'],
        'AZ': ['CA', 'NV', 'UT', 'NM'],
        'MT': ['ID', 'WY', 'SD', 'ND'],
        'WY': ['MT', 'ID', 'UT', 'CO', 'SD', 'NE'],
        'CO': ['WY', 'UT', 'AZ', 'NM', 'OK', 'KS', 'NE'],
        'NM': ['AZ', 'CO', 'OK', 'TX'],
        'ND': ['MT', 'SD', 'MN'],
        'SD': ['ND', 'MT', 'WY', 'NE', 'MN', 'IA'],
        'NE': ['SD', 'WY', 'CO', 'KS', 'IA', 'MO'],
        'KS': ['NE', 'CO', 'OK', 'MO'],
        'OK': ['KS', 'CO', 'NM', 'TX', 'AR', 'MO'],
        'TX': ['NM', 'OK', 'AR', 'LA'],
        'MN': ['ND', 'SD', 'IA', 'WI'],
        'IA': ['MN', 'SD', 'NE', 'MO', 'WI', 'IL'],
        'MO': ['IA', 'NE', 'KS', 'OK', 'AR', 'TN', 'KY', 'IL'],
        'AR': ['MO', 'OK', 'TX', 'LA', 'MS', 'TN'],
        'LA': ['TX', 'AR', 'MS'],
        'WI': ['MN', 'IA', 'IL', 'MI'],
        'IL': ['WI', 'IA', 'MO', 'KY', 'IN'],
        'MI': ['WI', 'IN', 'OH'],
    }
    return states
def solve_map_coloring():
    """解决地图着色问题"""
    states = create_map_coloring_problem()
    # 创建图
    G = nx.Graph(states)
    # 使用贪心算法着色
    coloring = nx.greedy_color(G, strategy='largest_first')
    print("地图着色结果：")
    for state, color in sorted(coloring.items()):
        print(f"{state} -> 颜色 {color}")
    print(f"\n总共使用了 {len(set(coloring.values()))} 种颜色")
    # 可视化
    plt.figure(figsize=(12, 8))
    pos = nx.spring_layout(G, k=0.5, iterations=50)
    # 颜色映射
    cmap = plt.cm.Set3
    colors = [coloring[state] for state in G.nodes()]
    color_list = [cmap(c/len(set(colors))) for c in colors]
    nx.draw(G, pos, 
            node_color=color_list,
            node_size=2000,
            with_labels=True,
            font_size=10,
            font_weight='bold')
    plt.title("美国西部地图着色问题")
    plt.show()
if __name__ == "__main__":
    solve_map_coloring()

这些代码展示了三种不同的图着色方法：

1. 贪心算法 - 简单高效，但可能不是最优解
2. DSATUR算法 - 更优化的着色，通常能得到更好的结果
3. Scikit-learn方法 - 利用机器学习中的谱聚类进行着色

每种方法都包含可视化功能,可以帮助理解图着色的结果，实际应用中，可以根据图的规模和复杂度选择合适的方法。