Wie implementiert man Kruskals Algorithmus mit Python?

Wie implementiert man Kruskals Algorithmus mit Python?

Einführung:
Kruskals Algorithmus ist ein klassischer Algorithmus zur Lösung des minimalen Spannbaums, der den Spannbaum mit dem minimalen Gesamtgewicht in einem gegebenen gewichteten verbundenen Diagramm finden kann. In diesem Artikel wird die Implementierung des Kruskal-Algorithmus mit Python vorgestellt und detaillierte Codebeispiele bereitgestellt.

1. Einführung in den Algorithmus:
   Die Grundidee des Kruskal-Algorithmus besteht darin, alle Kanten im verbundenen Diagramm nach ihrem Gewicht zu sortieren und dann die Kanten von klein nach groß auszuwählen, wenn die aktuell ausgewählte Kante nicht gebildet wird ein Zyklus, dann wird es dem minimalen Spannbaum beitreten und ihn als besucht markieren. Bis die Anzahl der Kanten im minimalen Spannbaum gleich der Anzahl der Eckpunkte im Diagramm minus eins ist.
2. Implementierungsschritte:
   (1) Definieren Sie die Klasse des Diagramms und initialisieren Sie die Anzahl der Scheitelpunkte und Kanten des Diagramms.
   (2) Definieren Sie die Klasse jeder Kante und initialisieren Sie den Startpunkt, den Endpunkt und das Gewicht der Kante.
   (3) Schreiben Sie eine Funktion zum Implementieren und Initialisieren des Satzes, einschließlich der Suche nach dem Wurzelknoten und dem Zusammenführen von Sätzen.
   (4) Schreiben Sie die Hauptfunktion zur Implementierung des Kruskal-Algorithmus, einschließlich Sortieren von Kanten, Auswahl von Kanten nacheinander, um zu bestimmen, ob sie einen Zyklus bilden, Hinzufügen von Kanten zum minimalen Spannbaum und Berechnen des Gesamtgewichts des minimalen Spannbaums.
3. Codebeispiel:

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数
        self.graph = []

    # 添加边
    def add_edge(self, u, v, weight):
        self.graph.append([u, v, weight])

    # 查找根节点
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    # 合并集合
    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    # 克鲁斯卡尔算法
    def kruskal_algorithm(self):
        result = []
        i = 0
        e = 0
        self.graph = sorted(self.graph, key=lambda item: item[2])  # 按照权值排序
        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, weight = self.graph[i]
            i += 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e += 1
                result.append([u, v, weight])
                self.union(parent, rank, x, y)

        # 打印最小生成树
        print("最小生成树：")
        for u, v, weight in result:
            print(f"{u} -- {v}     {weight}")

        # 计算最小生成树的总权值
        total_weight = sum(weight for u, v, weight in result)
        print("最小生成树的总权值：", total_weight)


if __name__ == '__main__':
    g = Graph(6)
    g.add_edge(0, 1, 4)
    g.add_edge(0, 2, 3)
    g.add_edge(1, 2, 1)
    g.add_edge(1, 3, 2)
    g.add_edge(2, 3, 4)
    g.add_edge(2, 4, 3)
    g.add_edge(3, 4, 2)
    g.add_edge(3, 5, 1)
    g.add_edge(4, 5, 6)

    g.kruskal_algorithm()

4. Ergebnisanalyse:
   Der obige Code ist ein typisches Beispiel, bei dem ein gewichteter ungerichteter Graph mit 6 Eckpunkten erstellt und der Kruskal-Algorithmus verwendet wird, um seinen minimalen Spannbaum zu lösen. Das Programm gibt die Kanten im minimalen Spannbaum und das Gesamtgewicht des minimalen Spannbaums aus.

Fazit:
Kruskals Algorithmus ist eine effiziente Methode, um den minimalen Spannbaum eines verbundenen Graphen zu lösen. Durch Sortieren der Kanten und Zusammenführen von Mengen kann ein Spannbaum mit dem minimalen Gesamtgewicht erhalten werden. Die Verwendung von Python zur Implementierung des Kruskal-Algorithmus kann uns helfen, die Prinzipien und Prozesse des Algorithmus besser zu verstehen und ihn einfach auf praktische Probleme anzuwenden.

Das obige ist der detaillierte Inhalt vonWie implementiert man Kruskals Algorithmus mit Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!