用Python实现three_color方法：返回图的所有顶点着色组合（含无效）

Got it, let's break down how to implement the three_color(graph) function you need. The core requirement here is to generate every possible color assignment for the graph's vertices—even those where adjacent nodes share the same color—since the problem explicitly says to include invalid combinations.

Approach #

Each vertex has exactly 3 color options (we'll use 1, 2, 3 as the color values). For a graph with n vertices, the total number of combinations is 3^n. Here's how to generate them:

• Extract all vertex names from the input graph (these are the keys of the input dictionary).
• Generate every possible sequence of 3 colors, with length equal to the number of vertices. This is a classic Cartesian product problem, which Python's itertools.product handles perfectly.
• Convert each color sequence into a dictionary where each vertex maps to its assigned color.
• Collect all these dictionaries into a list and return it.

Python Implementation #

import itertools

def three_color(graph):
    # Get the list of vertices from the graph's keys
    vertices = list(graph.keys())
    # Generate all possible color combinations (each vertex has 3 choices)
    color_tuples = itertools.product([1, 2, 3], repeat=len(vertices))
    # Convert each tuple to a vertex-color dictionary
    return [dict(zip(vertices, combo)) for combo in color_tuples]

Testing the Example #

Let's test the function with your sample input:

# Test case: graph with two connected nodes A and B
sample_graph = {"A": ["B"], "B": ["A"]}
all_combinations = three_color(sample_graph)

# Print the result (should have 9 entries)
for combo in all_combinations:
    print(combo)

This will output all 9 possible combinations, including:

• {"A": 1, "B": 1} (invalid, adjacent same color)
• {"A": 1, "B": 2} (valid)
• ... and all other 3×3 permutations.

Why This Works #

• itertools.product([1,2,3], repeat=len(vertices)) generates every possible ordered sequence of colors, where each position in the sequence corresponds to a vertex in the vertices list.
• dict(zip(vertices, combo)) pairs each vertex with its color from the sequence, creating the required dictionary structure.
• We don't need any logic to check if the coloring is valid because the problem explicitly asks to include all combinations—even the invalid ones.

内容的提问来源于stack exchange，提问作者Shrebble