Colors a graph so that no two adjacent vertices share the same color using a backtracking approach.

# Graph Coloring - Backtracking # Description: Colors a graph so that no two adjacent vertices share the same color using a backtracking approach. def graph_coloring(graph, num_colors): """ Color a graph using backtracking to ensure no adjacent nodes share a color. This algorithm attempts to assign colors to graph nodes such that no two adjacent nodes have the same color, using the minimum number of colors possible. Args: graph (dict): Adjacency list representing graph connections. num_colors (int): Maximum number of colors available for coloring. Returns: dict: Mapping of nodes to colors, or None if no valid coloring exists. Time Complexity: O(num_colors^V), where V is the number of vertices Space Complexity: O(V) Note: This is an NP-hard problem, so the algorithm uses backtracking. """ # Initialize coloring with uncolored nodes coloring = {node: -1 for node in graph} nodes = list(graph.keys()) def is_color_valid(node, color): """ Check if a color can be assigned to a node without conflicts. Args: node (int): Current node being colored color (int): Color being considered Returns: bool: True if color can be assigned, False otherwise """ # Check all adjacent nodes to ensure no color conflicts for neighbor in graph[node]: # Skip uncolored neighbors if coloring[neighbor] == -1: continue # Check for color conflict with colored neighbors if coloring[neighbor] == color: return False return True def backtrack_color(node_index): """ Recursive backtracking function to color the graph. Args: node_index (int): Index of the current node being processed Returns: bool: True if a valid coloring is found, False otherwise """ # Base case: all nodes have been colored successfully if node_index == len(nodes): return True # Get the current node to color current_node = nodes[node_index] # Try coloring the current node with each available color for color in range(num_colors): # Check if the current color is valid for this node if is_color_valid(current_node, color): # Assign the color coloring[current_node] = color # Recursively try to color the next node if backtrack_color(node_index + 1): return True # Backtrack: reset the color if solution not found coloring[current_node] = -1 # No valid coloring found return False # Attempt to color the graph return coloring if backtrack_color(0) else None

Mar 28, 2025 - 04:49

# Graph Coloring - Backtracking
# Description: Colors a graph so that no two adjacent vertices share the same color using a backtracking approach.

def graph_coloring(graph, num_colors):
    """
    Color a graph using backtracking to ensure no adjacent nodes share a color.

    This algorithm attempts to assign colors to graph nodes such that no 
    two adjacent nodes have the same color, using the minimum number of colors possible.

    Args:
        graph (dict): Adjacency list representing graph connections.
        num_colors (int): Maximum number of colors available for coloring.

    Returns:
        dict: Mapping of nodes to colors, or None if no valid coloring exists.

    Time Complexity: O(num_colors^V), where V is the number of vertices
    Space Complexity: O(V)

    Note: This is an NP-hard problem, so the algorithm uses backtracking.
    """
    # Initialize coloring with uncolored nodes
    coloring = {node: -1 for node in graph}
    nodes = list(graph.keys())

    def is_color_valid(node, color):
        """
        Check if a color can be assigned to a node without conflicts.

        Args:
            node (int): Current node being colored
            color (int): Color being considered

        Returns:
            bool: True if color can be assigned, False otherwise
        """
        # Check all adjacent nodes to ensure no color conflicts
        for neighbor in graph[node]:
            # Skip uncolored neighbors
            if coloring[neighbor] == -1:
                continue
            # Check for color conflict with colored neighbors
            if coloring[neighbor] == color:
                return False
        return True

    def backtrack_color(node_index):
        """
        Recursive backtracking function to color the graph.

        Args:
            node_index (int): Index of the current node being processed

        Returns:
            bool: True if a valid coloring is found, False otherwise
        """
        # Base case: all nodes have been colored successfully
        if node_index == len(nodes):
            return True

        # Get the current node to color
        current_node = nodes[node_index]

        # Try coloring the current node with each available color
        for color in range(num_colors):
            # Check if the current color is valid for this node
            if is_color_valid(current_node, color):
                # Assign the color
                coloring[current_node] = color

                # Recursively try to color the next node
                if backtrack_color(node_index + 1):
                    return True

                # Backtrack: reset the color if solution not found
                coloring[current_node] = -1

        # No valid coloring found
        return False

    # Attempt to color the graph
    return coloring if backtrack_color(0) else None