判定图中是否存在k-圈的有效近似算法

import random

def random_walk(graph, start, k):
    path = [start]
    current_vertex = start
    for _ in range(k):
        neighbors = graph[current_vertex]
        if not neighbors:
            break
        next_vertex = random.choice(neighbors)
        path.append(next_vertex)
        current_vertex = next_vertex
    return path

def approximate_k_clique(graph, k, num_walks=1000):
    vertices = list(graph.keys())
    for _ in range(num_walks):
        start_vertex = random.choice(vertices)
        path = random_walk(graph, start_vertex, k)
        if len(set(path)) == k and all(vertex in graph[path[-1]] for vertex in path[:-1]):
            return True
    return False

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

k = 3
print(approximate_k_clique(graph, k))  # 输出: True 或 False