博客

普里姆算法

普里姆算法（Prim’s Algorithm）是一种用于求解无向图的最小生成树的贪心算法。所谓最小生成树，是指一个加权无向图中生成一棵生成树，且所有边的权值和最小的生成树。

算法步骤

1. 将一个任意节点加入到生成树中。
2. 重复以下步骤，直到所有节点都已被加入到生成树中：
3. 从生成树中的所有节点，找到一条连接着未被访问过的节点的最小权值的边。
4. 将此边加入到生成树中。

使用方法

输入一个加权无向图，运行普里姆算法，即可得到生成树。

• 输入

graph = {
0: {1: 2, 3: 6},
1: {0: 2, 2: 3, 3: 8},
2: {1: 3},
3: {0: 6, 1: 8}
}

上述图表示了一个有4个节点，5条边的无向图，每条边都有加权值。

• 运行

“`
def prim_mst(graph):
# 选取一个任意节点作为起点
start = list(graph.keys())[0]

  # 保存已经加入到生成树中的节点
  added_nodes = set([start])

  # 用于保存生成树的边
  mst = []

  while len(added_nodes) < len(graph):
      # 可以用来连接新节点的边和权值
      min_edge = None
      min_weight = float('inf')

      # 在已加入的节点中查找连接新节点的最小边
      for node in added_nodes:
          for new_node, weight in graph[node].items():
              if new_node not in added_nodes and weight < min_weight:
                  min_edge = (node, new_node)
                  min_weight = weight

      # 将新节点和边加入到生成树中
      added_nodes.add(min_edge[1])
      mst.append(min_edge)

  return mst

mst = prim_mst(graph)
“`

• 输出

[(0, 1), (1, 2), (0, 3)]

上述输出结果表示生成树为由节点0和1、1和2、0和3三条边组成。

示例

示例一

输入一个六个节点八条边的加权无向图：

graph = {
    0: {1: 1, 2: 2, 3: 7},
    1: {0: 1, 3: 4},
    2: {0: 2, 3: 5, 4: 3},
    3: {0: 7, 1: 4, 2: 5, 4: 6, 5: 3},
    4: {2: 3, 3: 6, 5: 8},
    5: {3: 3, 4: 8}
}

运行后得到的生成树为：

[(1, 0), (2, 0), (4, 2), (3, 5), (3, 1)]

示例二

输入一个四个节点五条边的加权无向图：

graph = {
    0: {1: 2, 2: 3},
    1: {0: 2, 2: 4, 3: 2},
    2: {0: 3, 1: 4, 3: 5},
    3: {1: 2, 2: 5}
}

运行后得到的生成树为：

[(0, 1), (1, 3), (0, 2)]

总结

普里姆算法是一种简单易懂的求解无向图最小生成树的方法。虽然其时间复杂度较高，但比起其他的方法来说，普里姆算法的实现相对较简单，其对初学者而言编写难度较小。在实际应用中，普里姆算法可以用于城市间的最小制作通路问题，街道交通优化、动态公交线路优化等问题。