查找图中指定长度范围内的简单环：一种实用教程

from collections import deque

def find_cycles_with_node(graph, start_node, max_length):
    """
    Finds all simple cycles containing a given node with length up to max_length using BFS.

    Args:
        graph: A dictionary representing the graph, where keys are nodes and values are lists of neighbors.
        start_node: The node to search for cycles containing.
        max_length: The maximum length of the cycles to find.

    Returns:
        A list of cycles (lists of nodes) containing the start_node.
    """
    cycles = []
    queue = deque([(start_node, [start_node])])  # (node, path)

    while queue:
        node, path = queue.popleft()

        for neighbor in graph[node]:
            if neighbor == start_node and len(path) <= max_length and len(set(path)) == len(path):
                cycles.append(path + [neighbor])  # Cycle found
            elif neighbor not in path and len(path) < max_length:
                queue.append((neighbor, path + [neighbor]))

    # Remove duplicates and cycles that are just rotations of each other
    unique_cycles = []
    for cycle in cycles:
        cycle = tuple(cycle)
        is_rotation = False
        for unique_cycle in unique_cycles:
            if len(cycle) == len(unique_cycle):
                for i in range(len(cycle)):
                    rotated_cycle = cycle[i:] + cycle[:i]
                    if rotated_cycle == unique_cycle:
                        is_rotation = True
                        break
                if is_rotation:
                    break
        if not is_rotation:
            unique_cycles.append(cycle)

    return unique_cycles


# Example Usage:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

start_node = 'A'
max_length = 4
cycles = find_cycles_with_node(graph, start_node, max_length)

print(f"Cycles containing node {start_node} with length up to {max_length}:")
for cycle in cycles:
    print(cycle)