使用Python对字典关联值分组，生成含组号的新字典

Looks like you need to identify connected components in your graph of squares and map each square to its corresponding group ID. This is a classic graph traversal problem—we can use either BFS (Breadth-First Search) or DFS (Depth-First Search) to solve it efficiently.

Approach #

Here's a step-by-step breakdown of how to do this:

• Track visited nodes: Use a set to keep track of squares we've already processed so we don't reprocess them.
• Iterate through each square: For every square that hasn't been visited yet, start a traversal to find all connected squares.
• Assign group IDs: All squares in the same connected component get the same group number. We increment the group number each time we finish processing a new component.

Solution Code #

Let's implement this with BFS (it's great for avoiding recursion depth issues with large graphs):

def map_connected_groups(graph):
    visited = set()
    group_mapping = {}
    current_group = 1
    
    # Iterate over each square in the original dictionary
    for square in graph:
        if square not in visited:
            # Start BFS to find all connected squares in this component
            queue = [square]
            visited.add(square)
            
            while queue:
                current_square = queue.pop(0)
                # Assign the current group number to this square
                group_mapping[current_square] = current_group
                
                # Add all connected neighbors to the queue if not visited
                for neighbor in graph[current_square]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            
            # Move to the next group for the next component
            current_group += 1
    
    return group_mapping

# Example usage with your provided dictionary
square_graph = {
    1: [4],
    2: [3, 5],
    3: [2, 5],
    4: [1, 6],
    5: [2, 3],
    6: [4, 8],
    7: [9, 10],
    8: [6, 11],
    9: [7, 10],
    10: [7, 9],
    11: [8]
}

# Generate the group mapping
result = map_connected_groups(square_graph)
print(result)

Output #

Running this code will give you the following result, where each key is a square number and the value is its group ID:

{1: 1, 4: 1, 6: 1, 8: 1, 11: 1, 2: 2, 3: 2, 5: 2, 7: 3, 9: 3, 10: 3}

Alternative: DFS Implementation #

If you prefer using DFS (recursive approach), here's a quick alternative—just note that for very large graphs, you might hit Python's recursion limit:

def map_connected_groups_dfs(graph):
    visited = set()
    group_mapping = {}
    current_group = 1
    
    def dfs(node):
        visited.add(node)
        group_mapping[node] = current_group
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
    
    for square in graph:
        if square not in visited:
            dfs(square)
            current_group += 1
    
    return group_mapping

Both approaches will correctly group your connected squares. The BFS method is generally safer for larger datasets, while the DFS approach is more concise.

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