如何修改回溯算法以遍历所有起始节点查找k顶点简单环

问题分析 #

原代码仅从指定的单个起始节点出发搜索k顶点简单环，当目标环的所有顶点都不在该起始节点的搜索路径中时，会出现漏判（比如示例图中k=3的环仅能从节点2、3、4出发找到）。需要新增外层逻辑，遍历所有可能的起始节点进行检测。

修改后的代码 #

def simpleCycle(A, k, visited, currentNode):
    visited.append(currentNode)
    
    # 找到长度为k的环：当前节点与起始节点相连
    if len(visited) == k and A[currentNode][visited[0]] == 1:
        return True
    
    # 遍历所有邻居，仅访问未去过的节点且路径长度未达k
    for neighbor in range(len(A[currentNode])):
        if neighbor not in visited and A[currentNode][neighbor] == 1 and len(visited) < k:
            if simpleCycle(A, k, visited, neighbor):
                return True
    
    # 回溯：移除当前节点
    visited.pop()
    return False

def has_k_vertex_cycle(A, k):
    n = len(A)
    # 简单环至少需要3个顶点，k<3或k超过总顶点数直接返回False
    if k < 3 or k > n:
        return False
    
    # 遍历每个节点作为起始点
    for start_node in range(n):
        # 每次搜索使用全新的visited列表，避免跨起始点的状态污染
        if simpleCycle(A, k, [], start_node):
            return True
    return False

# 示例邻接矩阵
A = [[0, 1, 0, 1, 0],
     [1, 0, 1, 0, 0],
     [0, 1, 0, 1, 1],
     [1, 0, 1, 0, 1],
     [0, 0, 1, 1, 0]]

# 测试用例
print(has_k_vertex_cycle(A, 3))  # 输出True
print(has_k_vertex_cycle(A, 4))  # 输出True
print(has_k_vertex_cycle(A, 5))  # 输出True

关键改动说明 #

• 新增has_k_vertex_cycle外层函数，负责遍历图中所有节点作为起始点调用回溯函数
• 每次调用simpleCycle时传入全新的空visited列表，避免不同起始点的搜索状态互相干扰
• 增加边界条件判断：过滤掉k小于3（简单环的最小顶点数）或大于图总顶点数的无效情况
• 只要有任意一个起始点能找到符合要求的环，立即返回True，无需继续遍历

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