问题一：度启发式
度启发式是选择与最多其他变量相邻的变量进行赋值。在图中，SA与最多的其他省份相邻（WA、NT、Q、NSW、V），因此应该先给SA赋值。

# 定义图的邻接表
graph = {
    'WA': ['NT', 'SA'],
    'NT': ['WA', 'Q', 'SA'],
    'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
    'Q': ['NT', 'SA', 'NSW'],
    'NSW': ['Q', 'SA', 'V'],
    'V': ['SA', 'NSW'],
    'T': []
}

# 定义可用的颜色
colors = ['red', 'green', 'blue']

# 打印图的结构
for region, neighbors in graph.items():
    print(f"{region}: {neighbors}")

def degree_heuristic(graph):
    # 计算每个变量的度
    degree = {region: len(neighbors) for region, neighbors in graph.items()}
    # 找到度最大的变量
    max_degree_variable = max(degree, key=degree.get)
    return max_degree_variable, degree[max_degree_variable]

# 使用度启发式选择变量
selected_variable, max_degree = degree_heuristic(graph)
print(f"\n选择的变量是: {selected_variable}")
print(f"它的度为：{max_degree}")

WA: ['NT', 'SA']
NT: ['WA', 'Q', 'SA']
SA: ['WA', 'NT', 'Q', 'NSW', 'V']
Q: ['NT', 'SA', 'NSW']
NSW: ['Q', 'SA', 'V']
V: ['SA', 'NSW']
T: []

选择的变量是: SA
它的度为：5

问题二：MRV启发式
MRV启发式选择剩余可用颜色最少的变量。此时，SA和Q都与NT相邻，NT已经是绿色，因此SA和Q都不能是绿色。由于WA是红色，SA不能是红色。Q没有与WA相邻，所以Q可以是红色或蓝色。SA剩余的颜色只有蓝色。因此，应该选择SA进行赋值。
解决方案一：

# 定义图的邻接表
graph = {
    'WA': ['NT', 'SA'],
    'NT': ['WA', 'Q', 'SA'],
    'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
    'Q': ['NT', 'SA', 'NSW'],
    'NSW': ['Q', 'SA', 'V'],
    'V': ['SA', 'NSW'],
    'T': []
}

# 定义可用的颜色
colors = ['red', 'green', 'blue']

# 已有的部分赋值
partial_assignment = {
    'WA': 'red',
    'NT': 'green'
}

def mrv_heuristic(graph, colors, partial_assignment):
    # 记录每个未赋值变量的剩余可用颜色数
    remaining_values = {}
    for region in graph:
        if region not in partial_assignment:
            # 找出相邻已赋值的颜色
            used_colors = set()
            for neighbor in graph[region]:
                if neighbor in partial_assignment:
                    used_colors.add(partial_assignment[neighbor])
            
            # 计算剩余可用颜色
            remaining_colors = [color for color in colors if color not in used_colors]
            remaining_values[region] = len(remaining_colors)
    
    # 打印每个节点的剩余可用颜色数
    for region, count in remaining_values.items():
        print(f"{region} 的剩余可用颜色数: {count}")
    
    # 找到剩余可用颜色最少的变量
    mrv_variable = min(remaining_values, key=remaining_values.get)
    return mrv_variable

# 使用MRV启发式选择变量
selected_variable = mrv_heuristic(graph, colors, partial_assignment)
print(f"选择的变量是: {selected_variable}")

SA 的剩余可用颜色数: 1
Q 的剩余可用颜色数: 2
NSW 的剩余可用颜色数: 3
V 的剩余可用颜色数: 3
T 的剩余可用颜色数: 3
选择的变量是: SA

可以进一步简化代码，得到解决方案二。

解决方案二：

# 定义图的邻接表
graph = {
    'WA': ['NT', 'SA'],
    'NT': ['WA', 'Q', 'SA'],
    'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
    'Q': ['NT', 'SA', 'NSW'],
    'NSW': ['Q', 'SA', 'V'],
    'V': ['SA', 'NSW'],
    'T': []
}

# 定义可用的颜色
colors = ['red', 'green', 'blue']

# 已有的部分赋值
partial_assignment = {
    'WA': 'red',
    'NT': 'green'
}

def mrv_heuristic(graph, colors, partial_assignment):
    # 记录每个未赋值变量的剩余可用颜色数
    remaining_values = {}
    for region in graph:
        if region not in partial_assignment:
            # 找出相邻已赋值的颜色
            used_colors = {partial_assignment[neighbor] for neighbor in graph[region] if neighbor in partial_assignment}
            # 计算剩余可用颜色
            remaining_colors = [color for color in colors if color not in used_colors]
            remaining_values[region] = len(remaining_colors)
    
    # 打印每个节点的剩余可用颜色数
    for region, count in remaining_values.items():
        print(f"{region} 的剩余可用颜色数: {count}")
    
    # 找到剩余可用颜色最少的变量
    mrv_variable = min(remaining_values, key=remaining_values.get)
    #print(mrv_variable)
    return mrv_variable

# 使用MRV启发式选择变量
selected_variable = mrv_heuristic(graph, colors, partial_assignment)
print(f"选择的变量是: {selected_variable}")

SA 的剩余可用颜色数: 1
Q 的剩余可用颜色数: 2
NSW 的剩余可用颜色数: 3
V 的剩余可用颜色数: 3
T 的剩余可用颜色数: 3
选择的变量是: SA

问题三：冲突集
SA与Q、NSW、V相邻。Q是红色，NSW是绿色，V是蓝色。因此，SA没有可用的颜色。SA的冲突集是与其相邻且已赋值的变量集合，即 {Q, NSW, V}。

# 定义图的邻接表
graph = {
    'WA': ['NT', 'SA'],
    'NT': ['WA', 'Q', 'SA'],
    'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
    'Q': ['NT', 'SA', 'NSW'],
    'NSW': ['Q', 'SA', 'V'],
    'V': ['SA', 'NSW'],
    'T': []
}

# 已有的部分赋值
partial_assignment = {
    'Q': 'red',
    'NSW': 'green',
    'V': 'blue',
    'T': 'red'
}

def find_conflict_set(graph, partial_assignment, target):
    # 找出与目标节点相邻且已赋值的节点
    conflict_set = {neighbor for neighbor in graph[target] if neighbor in partial_assignment}
    return conflict_set

# 找出SA的冲突集
conflict_set = find_conflict_set(graph, partial_assignment, 'SA')
print(f"SA的冲突集是: {conflict_set}")

SA的冲突集是: {'V', 'Q', 'NSW'}