Python实现图着色算法动态可视化

图着色算法动态可视化APP

图着色问题是为图中的顶点分配颜色，使得相邻顶点颜色不同。下面是一个基于回溯法的动态可视化实现：

算法核心逻辑

可视化设计

代码实现

import pygame
import sys
import time

# 初始化pygame
pygame.init()

# 图结构示例
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
}

# 顶点位置（屏幕坐标）
positions = {
0: (100, 100),
1: (300, 100),
2: (200, 300),
3: (200, 500)
}

# 颜色池
COLORS = [(255, 0, 0), (0, 255, 0), (0, 0, 255), (255, 255, 0)]

# 屏幕设置
WIDTH, HEIGHT = 600, 600
screen = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption("图着色动态可视化")

# 顶点着色状态
vertex_color = {v: None for v in graph}

def is_safe(v, color):
"""检查顶点v能否使用颜色color"""
for neighbor in graph[v]:
if vertex_color[neighbor] == color:
return False
return True

def draw_graph(highlight_edge=None):
"""绘制图结构"""
screen.fill((255, 255, 255))

# 绘制边
for v in graph:
for u in graph[v]:
pygame.draw.line(screen, (0, 0, 0), positions[v], positions[u], 2)

# 绘制顶点
for v, pos in positions.items():
color = vertex_color[v] if vertex_color[v] is not None else (200, 200, 200)
pygame.draw.circle(screen, color, pos, 30)
font = pygame.font.SysFont(None, 24)
text = font.render(str(v), True, (0, 0, 0))
screen.blit(text, (pos[0]-10, pos[1]-10))

# 高亮冲突边
if highlight_edge:
pygame.draw.line(screen, (255, 0, 0), highlight_edge[0], highlight_edge[1], 4)

pygame.display.flip()

def graph_coloring():
"""回溯法着色（动态可视化）"""
vertices = list(graph.keys())

def backtrack(v_idx):
if v_idx == len(vertices):
return True

v = vertices[v_idx]
for color in COLORS:
if is_safe(v, color):
vertex_color[v] = color
draw_graph()
time.sleep(1.0) # 暂停观察

if backtrack(v_idx + 1):
return True

# 回溯
vertex_color[v] = None
draw_graph()
time.sleep(0.5)
else:
# 显示冲突
for neighbor in graph[v]:
if vertex_color.get(neighbor) == color:
draw_graph(highlight_edge=(positions[v], positions[neighbor]))
time.sleep(1.0)
return False

return backtrack(0)

# 主循环
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False

# 启动着色
graph_coloring()
pygame.time.delay(3000) # 完成后暂停3秒
running = False

pygame.quit()
sys.exit()

功能说明

扩展方向

此APP通过可视化帮助理解图着色算法的执行过程，适合教学或调试场景。