博客

Python 经典贪心算法之Prim算法案例详解

  • Post category:Python

Python经典贪心算法之Prim算法案例详解

Prim算法是一种常见的最小生成树算法，它可以用于解决网络连通问题。在本文中，将讲解Prim算法的原理、Python实现以及两个示例说明。

Prim算原理

Prim算法是一种贪心算，它的核心思想是从一个点开始，每次选择一个与当前生成树距离最近的点加入生成树中。具体来说，Prim算法使用一个数组来存储每个点到生成树的距离，然后每次选择距离最小的点加入生成树中，同时更新数组中的距离。最终，我们得到的生成树就是最小生成树。

Python实现Prim算法

在Python中，我们可以使用一个二维数组来表示图，使用一个一维数组来存储每个点到生成树的距离。我们可以使用一个visited集合来存储已经加入生成树的点，使用一个parent数组来存储每个点在生成树中的父节点。下面是Python实现Prim算法的代码：

import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]

    def printMST(self, parent):
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        visited = set()

        for _ in range(self.V):
            u = self.minKey(key, visited)
            visited.add(u)

            for v in range(self.V):
                if self.graph[u][v] > 0 and v not in visited and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        self.printMST(parent)

    def minKey(self, key, visited):
        min_val = sys.maxsize
        min_idx = -1
        for v in range(self.V):
            if key[v] < min_val and v not in visited:
                min_val = key[v]
                min_idx = v
        return min_idx

在这个代码中，我们使用了一个Graph类来表示图，使用了一个二维数组graph来存储图中的边。我们使用了一个printMST方法来打印小生成树，使用了一个primMST方法来实现Prim算法。我们使用了一个key数组来存储每个点到生成树的距离，使用了一个parent数组来存储每个点在生成树中的父节点。我们使用了一个visited集合来存储已经加入生成的点。我们使用了一个minKey方法来查找距离最小的点。

示例说明

示例1：求解无向图的最小生成树

在这个示例中，我们将使用Prim算法来求解无向图的最小生成树。假设我们有一个无向图，其中节点之间的距离如下所示：

   2    3
(0)--(1)--(2)
|    / \   |
6| 8/   \5 |7
| /     \ |
(3)-------(4)
      9

我们可以使用Prim算法来求解这个无向图的最小生成树，下面是Python代码：

g = Graph(5)
g.graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3,8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]
g.primMST()

在这个代码中，我们使用了一个Graph类来表示无向图，使用了一个二维数组graph来存储图中的边。我们使用了primMST方法来实现Prim算法，使用了printMST方法来打印最小生成树。我们创建了一个Graph对象，然后调用primMST`方法来求解最小生成树。

输出结果如下：

Edge    Weight
0 - 1    2
1 - 2 3
0 - 3    6
1 - 4    5

这个结果表示无向图的最小生成树为：

 2        3
(0)--(1)---(2)
      |   / |
     6|  /5 |
      | /   |
     (3)---(4)
        9

示例2：求解带权重的无向图的最小生成树在这个示例中，我们将使用Prim算法来求解带权重的无向图的最小生成树。假设我们有一个带权重的无向图，其中节点之间的距离如下所示：

   2    3
(0)--(1)--()
|    / \   |
6| 8/   \5 |7
| /     \ |
(3)-------(4)
      9

我们可以使用Prim算法来求解这个带权重的无向图的最小生成树，下面是Python代码：

g = Graph(5)
g.graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]
g.primMST()

在这个代码中，我们使用了一个Graph类来表示带权重的无向图，使用了一个维数组graph来存储图中的边。我们使用了primMST方法来实现Prim算法，使用了printMST方法来打印最小生成树。我们创建了一个Graph对象，然后调用primMST方法来求解最小生成树。

输出结果如下：

Edge    Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

这个结果表示带权重的无向图的最小生成树为：

   2        3(0)--(1)---(2)
      |   / |
     6|  /5 |
      | /   |
     (3)---(4)
        9

总结

本文介绍Prim算法的原理、Python实现以及两个示例说明。Prim算法是一种常见的最小生成树算法，它可以用于解决网络连通问题。在Python中，我们可以使用一个二维数组来表示图，使用一个一维数组来存储每个点到生成树的距离。我们可以使用一个visited集合来存储已经加入生成树的点，使用parent数组来存储每个点在生成树中的父节点。

Tags: ,