Comment implémenter l'algorithme de Kruskal en utilisant Python ?

Comment implémenter l'algorithme de Kruskal en utilisant Python ?

Introduction : 
L'algorithme de Kruskal est un algorithme classique pour résoudre l'arbre couvrant minimum, qui peut trouver l'arbre couvrant avec le poids total minimum dans un graphe connecté pondéré donné. Cet article présentera comment implémenter l'algorithme de Kruskal à l'aide de Python et fournira des exemples de code détaillés.

1. Introduction à l'algorithme :
   L'idée de base de l'algorithme de Kruskal est de trier toutes les arêtes du graphe connecté en fonction de leurs poids, puis de sélectionner les arêtes de petite à grande si l'arête actuelle sélectionnée ne se forme pas. un cycle, alors ce sera Rejoindre l'arbre couvrant minimum et le marquer comme visité. Jusqu'à ce que le nombre d'arêtes dans l'arbre couvrant minimum soit égal au nombre de sommets dans le graphe moins un.
2. Étapes de mise en œuvre :
   (1) Définir la classe du graphe et initialiser le nombre de sommets et d'arêtes du graphe.
   (2) Définissez la classe de chaque arête et initialisez le point de départ, le point final et le poids de l'arête.
   (3) Écrivez une fonction pour implémenter et initialiser l'ensemble, y compris la recherche du nœud racine et la fusion des ensembles.
   (4) Écrivez la fonction principale pour implémenter l'algorithme de Kruskal, y compris le tri des arêtes, la sélection des arêtes une par une pour déterminer si elles forment un cycle, l'ajout d'arêtes à l'arbre couvrant minimum et le calcul du poids total de l'arbre couvrant minimum.
3. Exemple de code :

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. Analyse des résultats :
   Le code ci-dessus est un exemple typique, construisant un graphe non orienté pondéré contenant 6 sommets et utilisant l'algorithme de Kruskal pour résoudre son arbre couvrant minimum. Le programme imprime les bords de l'arbre couvrant minimum et le poids total de l'arbre couvrant minimum.

Conclusion : 
L'algorithme de Kruskal est une méthode efficace pour résoudre l'arbre couvrant minimum d'un graphe connecté. En triant les arêtes et en fusionnant les ensembles, un arbre couvrant avec le poids total minimum peut être obtenu. Utiliser Python pour implémenter l'algorithme de Kruskal peut nous aider à mieux comprendre les principes et les processus de l'algorithme et à l'appliquer facilement à des problèmes pratiques.

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!