Comment écrire l'algorithme de Prim en Python ?

Comment écrire l'algorithme de Prim en Python ?

L'algorithme de Prim est un algorithme classique pour résoudre le problème de l'arbre couvrant minimum. Il peut trouver l'arbre couvrant minimum d'un graphe connecté non orienté. Cet article explique comment écrire l'algorithme de Prim à l'aide de Python, avec des exemples de code spécifiques.

Tout d'abord, nous devons comprendre les principes de base de l'algorithme de Prim. L'algorithme part d'un nœud de départ et étend progressivement les limites de l'arborescence jusqu'à ce que tous les nœuds du graphique soient couverts. Plus précisément, l'algorithme de Prim sélectionne à chaque fois un nœud le plus proche de l'arbre couvrant et l'ajoute à l'arbre couvrant, puis ajoute les arêtes reliant ce nœud aux nœuds de l'arbre couvrant à l'ensemble d'arêtes candidat. Ensuite, l’arête ayant le plus petit poids est sélectionnée parmi l’ensemble des arêtes candidates, et ce processus est répété jusqu’à ce que l’arbre couvrant contienne tous les nœuds.

Ce qui suit est un exemple de code d'utilisation de Python pour implémenter l'algorithme de Prim :

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()

Dans le code ci-dessus, une classe Graph est d'abord définie, qui contient les opérations de base du graphe. Dans la méthode primMST, la méthode minKey est utilisée pour sélectionner le nœud correspondant à l'arête avec le plus petit poids dans l'ensemble d'arêtes candidats, puis met à jour les tableaux de clés et parents.

Dans l'exemple de test, nous avons créé un graphe contenant 5 nœuds et donné sa représentation matricielle d'adjacence. La sortie du code correspond aux bords de l'arbre couvrant minimum et à leurs poids.

En bref, la simplicité et la lisibilité de Python rendent relativement facile la mise en œuvre de l'algorithme de Prim. En comprenant les principes de base de l'algorithme de Prim et en utilisant les exemples de code ci-dessus, vous pouvez facilement écrire et exécuter une implémentation de l'algorithme de Prim. J'espère que cet article vous aidera à apprendre l'algorithme de Prim !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!