当前位置：首页 > article >正文

使用 Prim 算法生成了最小生成树，使用 Fleury 算法生成了欧拉回路，尝试找到了一个简单的哈密尔顿圈。

article 2025/3/9 10:10:24

我们将分步骤完成建立全国各省会及一些主要城市的最简联通线路，利用 Prim 算法生成最小生成树，使用 Fleury 算法研究铁路线路回路方案，最后建立简单的哈密尔顿圈。

步骤 1：数据准备

首先，我们需要定义城市之间的连接信息和距离，这些信息将存储在邻接矩阵中。以下是一个简单的示例，假设我们有几个城市：

# 城市名称列表
cities = ["北京", "上海", "广州", "深圳", "成都"]

# 邻接矩阵表示城市之间的距离
graph = [
    [0, 1000, 1800, 1900, 1500],
    [1000, 0, 1200, 1300, 1600],
    [1800, 1200, 0, 100, 1200],
    [1900, 1300, 100, 0, 1300],
    [1500, 1600, 1200, 1300, 0]
]

步骤 2：Prim 算法生成最小生成树

Prim 算法是一种贪心算法，用于在加权无向图中找到最小生成树。以下是实现代码：

import sys

def prim(graph):
    num_vertices = len(graph)
    # 用于记录顶点是否已被访问
    visited = [False] * num_vertices
    # 存储最小生成树的边
    mst = []
    # 选择第一个顶点作为起始点
    visited[0] = True

    while len(mst) < num_vertices - 1:
        min_dist = sys.maxsize
        min_edge = None

        for i in range(num_vertices):
            if visited[i]:
                for j in range(num_vertices):
                    if not visited[j] and graph[i][j] > 0 and graph[i][j] < min_dist:
                        min_dist = graph[i][j]
                        min_edge = (i, j)

        if min_edge:
            mst.append(min_edge)
            visited[min_edge[1]] = True

    return mst

# 生成最小生成树
mst = prim(graph)
print("最小生成树的边：", mst)

步骤 3：Fleury 算法生成欧拉回路

Fleury 算法用于在连通图中找到欧拉回路。以下是实现代码：

def is_bridge(graph, u, v):
    # 检查边 (u, v) 是否为桥
    temp_graph = [row[:] for row in graph]
    temp_graph[u][v] = 0
    temp_graph[v][u] = 0

    visited = [False] * len(graph)
    stack = [u]
    visited[u] = True

    while stack:
        node = stack.pop()
        for neighbor in range(len(graph)):
            if temp_graph[node][neighbor] > 0 and not visited[neighbor]:
                stack.append(neighbor)
                visited[neighbor] = True

    return not all(visited)

def fleury(graph):
    num_vertices = len(graph)
    # 选择一个起始顶点
    start_vertex = 0
    circuit = []
    stack = [start_vertex]

    while stack:
        current_vertex = stack[-1]
        found_edge = False
        for neighbor in range(num_vertices):
            if graph[current_vertex][neighbor] > 0:
                if len(stack) == 1 or not is_bridge(graph, current_vertex, neighbor):
                    stack.append(neighbor)
                    graph[current_vertex][neighbor] = 0
                    graph[neighbor][current_vertex] = 0
                    found_edge = True
                    break
        if not found_edge:
            circuit.append(stack.pop())

    return circuit

# 复制最小生成树的图
mst_graph = [[0] * len(graph) for _ in range(len(graph))]
for u, v in mst:
    mst_graph[u][v] = graph[u][v]
    mst_graph[v][u] = graph[v][u]

# 生成欧拉回路
euler_circuit = fleury(mst_graph)
print("欧拉回路：", euler_circuit)

步骤 4：建立简单的哈密尔顿圈

哈密尔顿圈是一个遍历图中每个顶点恰好一次并回到起始顶点的回路。由于找到哈密尔顿圈是一个 NP 完全问题，我们可以使用简单的暴力搜索方法。以下是实现代码：

from itertools import permutations

def is_hamiltonian_cycle(graph, path):
    num_vertices = len(graph)
    if len(path) != num_vertices:
        return False
    for i in range(num_vertices - 1):
        if graph[path[i]][path[i + 1]] == 0:
            return False
    if graph[path[-1]][path[0]] == 0:
        return False
    return True

def find_hamiltonian_cycle(graph):
    num_vertices = len(graph)
    vertices = list(range(num_vertices))
    for perm in permutations(vertices[1:]):
        path = [vertices[0]] + list(perm)
        if is_hamiltonian_cycle(graph, path):
            path.append(path[0])
            return path
    return None

# 找到哈密尔顿圈
hamiltonian_cycle = find_hamiltonian_cycle(graph)
print("哈密尔顿圈：", hamiltonian_cycle)