Wie schreibe ich den Algorithmus von Prim in Python?

Wie schreibe ich Prims Algorithmus in Python?

Der Algorithmus von Prim ist ein klassischer Algorithmus zur Lösung des Minimum-Spanning-Tree-Problems. Er kann den Minimum-Spanning-Tree eines ungerichteten verbundenen Graphen finden. In diesem Artikel wird anhand spezifischer Codebeispiele erläutert, wie der Algorithmus von Prim mit Python geschrieben wird.

Zuerst müssen wir die Grundprinzipien des Prim-Algorithmus verstehen. Der Algorithmus beginnt bei einem Startknoten und erweitert schrittweise die Grenzen des Baums, bis alle Knoten im Diagramm abgedeckt sind. Insbesondere wählt der Prim-Algorithmus jedes Mal einen Knoten aus, der dem Baum am nächsten liegt, fügt ihn dem Spannbaum hinzu und fügt dann die Kanten, die diesen Knoten mit den Knoten im Spannbaum verbinden, dem Kandidatenkantensatz hinzu. Anschließend wird aus der Menge der Kandidatenkanten die Kante mit dem geringsten Gewicht ausgewählt und dieser Vorgang wiederholt, bis der Spannbaum alle Knoten enthält.

Das Folgende ist ein Codebeispiel für die Verwendung von Python zur Implementierung des Prim-Algorithmus:

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

Im obigen Code wird zunächst eine Graph-Klasse definiert, die die Grundoperationen des Graphen enthält. In der primMST-Methode wird die minKey-Methode verwendet, um den Knoten auszuwählen, der der Kante mit dem kleinsten Gewicht im Kandidatenkantensatz entspricht, und dann die Schlüssel- und übergeordneten Arrays zu aktualisieren.

Im Testbeispiel haben wir ein Diagramm mit 5 Knoten erstellt und dessen Adjazenzmatrixdarstellung angegeben. Die Ausgabe des Codes sind die Kanten des minimalen Spannbaums und ihre Gewichte.

Kurz gesagt, die Einfachheit und Lesbarkeit von Python machen es relativ einfach, den Algorithmus von Prim zu implementieren. Wenn Sie die Grundprinzipien des Prim-Algorithmus verstehen und die obigen Codebeispiele verwenden, können Sie problemlos eine Implementierung des Prim-Algorithmus schreiben und ausführen. Ich hoffe, dieser Artikel wird Ihnen helfen, den Algorithmus von Prim zu lernen!

Das obige ist der detaillierte Inhalt vonWie schreibe ich den Algorithmus von Prim in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!