四色问题穷举
def fourColors(areas, colors, close_areas, currentArea=1, result=list(), results=list()):
"""
四色问题暴力处理，枚举出一切可行的填色计划。需求传入总区域数和取色序列以及每个区域所邻接区域的字典。
:param areas: 总区域数
:param colors: 取色序列
:param close_areas: 一切区域所邻接区域的字典
:param currentArea: 当时填色区域
:param result: 填色成果列表
:param results: 填色成果总列表
:return: 填色成果总列表
"""
closeColors = set() # 当时区域所邻接区域一切填色的调集
for area in close_areas[currentArea]: # 遍历当时区域所邻接区域
if area < currentArea: # 当临界区域标号小于当时区域标号(避免超出result下标索引)
closeColors.add(result[area - 1]) # 从result中得到临界区域所填色增加进邻接区域填色调集
for color in colors: # 遍历取色序列
if color not in closeColors: # 若当时取色未在邻接区域一切填色调集中
result.append(color) # 将其增加进填色成果列表
if len(result) < areas: # 若填色成果列表已填色区域数小于总区域数
fourColors(areas, colors, close_areas, currentArea + 1, result, results) # 递归调用,当时填色区域号+1
elif len(result) == areas: # 若填色成果列表已填色区域数等于总区域数
results.append(result) # 填色成果增加进填色成果总列表
print(result) # 输出填色成果
result.pop() # 删去填色成果列表最终所填色,对当时区域进行下一次取色判别
return results
print("区域请以数字标号".center(50, "!"))
Areas = eval(input("请输入总区域数:"))
Colors = tuple(input("请输入一切取色(以英文逗号离隔):").split(","))
Close_areas = {}
for Area in range(1, Areas + 1):
Close_areas[Area] = eval((input(f"请输入区域 {Area} 所邻接的区域(以英文逗号离隔):")))
position = list()
for i in range(1, Areas + 1):
position.append(str(i))
print(position, "\t<序号符号>\n")
print(f"共有{len(fourColors(Areas, Colors, Close_areas))}种填色办法!")
四色问题回溯法处理
无向图如下：
区域图如下：
import numpy as np
color = 4 # 色彩种类
line = 0 # 从矩阵第零行开端着色
knot = 5 # 极点个数
color_list = np.zeros([1, 5]) # 每次染色的色彩次序
sum = 0 # 染色总数
def panduancolor(arr, line , color_list):
'''
:param arr: 输入邻接矩阵
:param line: 输入根结点，即从邻接矩阵榜首行开端
:param color_list: 填充色彩的次序
:return: 回来True or False
'''
for i in range(5): # 遍历一切的点一遍
if arr[line][i] != 0 and color_list[0][i] == color_list[0][line]: # 判别邻接矩阵中那个点色彩是否与相邻的区块色彩相同
return False # 与邻接区块有相同色彩则回来False
return True # 没有相同色彩则回来True
def caculatecolornum(arr, line, knot, color_list1):
'''
:param arr: 输入邻接矩阵
:param line: 输入根结点，即从邻接矩阵榜首行开端
:param knot: 输入总节点数
:param color_list1: 增加色彩的次序
:return: 回来增加完色彩后的色彩列表
'''
global sum
if line < knot: # 递归结束条件， 当邻接矩阵一切行都遍历完， 则递归结束
for i in range(1, color + 1): # 遍历一切的色彩一遍
color_list1[0][line] = i # 榜首个点赋值一种色彩后，使用递归查找树，找出其他点可能被赋予色彩的情况
if panduancolor(arr, line, color_list1): # 判别所赋值的色彩是否合法
caculatecolornum(arr, line + 1, knot, color_list1)
color_list1[0][line] = 0 # 恢复现场，即回来上一个节点，使上一个节点的色彩为空
else:
print(color_list[0])
sum += 1
group_arr = [[0, 1, 0, 0, 1],
[1, 0, 1, 0, 1],
[0, 1, 0, 1, 1],
[0, 0, 1, 0, 1],
[1, 1, 1, 1, 0]]
caculatecolornum(group_arr, 0, knot, color_list)
成果如下：
[1. 2. 1. 2. 3.]
[1. 2. 1. 2. 4.]
[1. 2. 1. 3. 4.]
[1. 2. 1. 4. 3.]
[1. 2. 3. 1. 4.]
[1. 2. 3. 2. 4.]
[1. 2. 4. 1. 3.]
[1. 2. 4. 2. 3.]
[1. 3. 1. 2. 4.]
[1. 3. 1. 3. 2.]
[1. 3. 1. 3. 4.]
[1. 3. 1. 4. 2.]
[1. 3. 2. 1. 4.]
[1. 3. 2. 3. 4.]
[1. 3. 4. 1. 2.]
[1. 3. 4. 3. 2.]
[1. 4. 1. 2. 3.]
[1. 4. 1. 3. 2.]
[1. 4. 1. 4. 2.]
[1. 4. 1. 4. 3.]
[1. 4. 2. 1. 3.]
[1. 4. 2. 4. 3.]
[1. 4. 3. 1. 2.]
[1. 4. 3. 4. 2.]
[2. 1. 2. 1. 3.]
[2. 1. 2. 1. 4.]
[2. 1. 2. 3. 4.]
[2. 1. 2. 4. 3.]
[2. 1. 3. 1. 4.]
[2. 1. 3. 2. 4.]
[2. 1. 4. 1. 3.]
[2. 1. 4. 2. 3.]
[2. 3. 1. 2. 4.]
[2. 3. 1. 3. 4.]
[2. 3. 2. 1. 4.]
[2. 3. 2. 3. 1.]
[2. 3. 2. 3. 4.]
[2. 3. 2. 4. 1.]
[2. 3. 4. 2. 1.]
[2. 3. 4. 3. 1.]
[2. 4. 1. 2. 3.]
[2. 4. 1. 4. 3.]
[2. 4. 2. 1. 3.]
[2. 4. 2. 3. 1.]
[2. 4. 2. 4. 1.]
[2. 4. 2. 4. 3.]
[2. 4. 3. 2. 1.]
[2. 4. 3. 4. 1.]
[3. 1. 2. 1. 4.]
[3. 1. 2. 3. 4.]
[3. 1. 3. 1. 2.]
[3. 1. 3. 1. 4.]
[3. 1. 3. 2. 4.]
[3. 1. 3. 4. 2.]
[3. 1. 4. 1. 2.]
[3. 1. 4. 3. 2.]
[3. 2. 1. 2. 4.]
[3. 2. 1. 3. 4.]
[3. 2. 3. 1. 4.]
[3. 2. 3. 2. 1.]
[3. 2. 3. 2. 4.]
[3. 2. 3. 4. 1.]
[3. 2. 4. 2. 1.]
[3. 2. 4. 3. 1.]
[3. 4. 1. 3. 2.]
[3. 4. 1. 4. 2.]
[3. 4. 2. 3. 1.]
[3. 4. 2. 4. 1.]
[3. 4. 3. 1. 2.]
[3. 4. 3. 2. 1.]
[3. 4. 3. 4. 1.]
[3. 4. 3. 4. 2.]
[4. 1. 2. 1. 3.]
[4. 1. 2. 4. 3.]
[4. 1. 3. 1. 2.]
[4. 1. 3. 4. 2.]
[4. 1. 4. 1. 2.]
[4. 1. 4. 1. 3.]
[4. 1. 4. 2. 3.]
[4. 1. 4. 3. 2.]
[4. 2. 1. 2. 3.]
[4. 2. 1. 4. 3.]
[4. 2. 3. 2. 1.]
[4. 2. 3. 4. 1.]
[4. 2. 4. 1. 3.]
[4. 2. 4. 2. 1.]
[4. 2. 4. 2. 3.]
[4. 2. 4. 3. 1.]
[4. 3. 1. 3. 2.]
[4. 3. 1. 4. 2.]
[4. 3. 2. 3. 1.]
[4. 3. 2. 4. 1.]
[4. 3. 4. 1. 2.]
[4. 3. 4. 2. 1.]
[4. 3. 4. 3. 1.]
[4. 3. 4. 3. 2.]
