NUMVC（最小顶点覆盖集）问题是图论中的一个经典问题，目标是找到图中最小的顶点集合，使得图中的每条边至少有一个端点在这个集合中。以下是使用Python实现的基于回溯法和贪心算法的代码示例： ### 回溯法实现 ```python def is_cover(graph, vertices): for u in graph: for v in graph[u]: if u not in vertices and v not in vertices: return False return True def backtrack(graph, index, current_cover, min_cover): if index == len(graph): if is_cover(graph, current_cover) and len(current_cover) < len(min_cover): min_cover[:] = current_cover.copy() return # 不选择当前顶点 backtrack(graph, index + 1, current_cover, min_cover) # 选择当前顶点 current_cover.append(list(graph.keys())[index]) backtrack(graph, index + 1, current_cover, min_cover) current_cover.pop() def min_vertex_cover_backtrack(graph): min_cover = list(graph.keys()) backtrack(graph, 0, [], min_cover) return min_cover # 示例图 graph = { 'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D'], 'D': ['B', 'C'] } result_backtrack = min_vertex_cover_backtrack(graph) print("回溯法得到的最小顶点覆盖集:", result_backtrack) ``` ### 贪心算法实现 ```python def min_vertex_cover_greedy(graph): cover = set() edges = [] for u in graph: for v in graph[u]: if (v, u) not in edges: edges.append((u, v)) while edges: max_degree_vertex = None max_degree = 0 for edge in edges: u, v = edge degree_u = len(graph[u]) degree_v = len(graph[v]) if degree_u > max_degree: max_degree = degree_u max_degree_vertex = u if degree_v > max_degree: max_degree = degree_v max_degree_vertex = v cover.add(max_degree_vertex) new_edges = [] for edge in edges: u, v = edge if max_degree_vertex not in [u, v]: new_edges.append(edge) edges = new_edges return cover result_greedy = min_vertex_cover_greedy(graph) print("贪心算法得到的最小顶点覆盖集:", result_greedy) ```