How to write Prim's algorithm in Python?

How to write Prim's algorithm in Python?

Prim's algorithm is a classic algorithm for solving the minimum spanning tree problem. It can find the minimum spanning tree of an undirected connected graph. This article will introduce how to write Prim's algorithm using Python, with specific code examples.

First of all, we need to understand the basic principles of Prim's algorithm. The algorithm starts from a starting node and gradually expands the boundaries of the tree until all nodes in the graph are covered. Specifically, Prim's algorithm selects a node closest to the tree each time and adds it to the spanning tree, and then adds the edges connecting this node to the nodes in the spanning tree to the candidate edge set. Then, the edge with the smallest weight is selected from the set of candidate edges, and this process is repeated until the spanning tree contains all nodes.

The following is a code example using Python to implement Prim's algorithm:

import sys

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

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

    def minKey(self, key, mstSet):
        min = sys.maxsize
        min_index = None

        for v in range(self.V):
            if key[v] < min and not mstSet[v]:
                min = key[v]
                min_index = v

        return min_index

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

        parent[0] = -1

        for _ in range(self.V):
            u = self.minKey(key, mstSet)
            mstSet[u] = True

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

        self.printMST(parent)

# 测试示例
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()

In the above code, a Graph class is first defined, which contains the basic operations of the graph. In the primMST method, the minKey method is used to select the node corresponding to the edge with the smallest weight in the candidate edge set, and then updates the key and parent arrays.

In the test example, we created a graph containing 5 nodes and gave its adjacency matrix representation. The output of the code is the edges of the minimum spanning tree and their weights.

In short, Python's simplicity and readability make it relatively easy to implement Prim's algorithm. By understanding the basic principles of Prim's algorithm and using the code examples above, you can easily write and run an implementation of Prim's algorithm. I hope this article will help you learn Prim's algorithm!

The above is the detailed content of How to write Prim's algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!