最小生成树的实验讲解

最小生成树是图论中的一个经典问题，它的应用非常广泛。下面是最小生成树的实验讲解：

1. Kruskal算法

Kruskal算法是一种基于贪心策略的算法，它的基本思想是将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入一条边会形成环，则不加入该边。直到生成树中的边数等于总顶点数减一或者测试完所有边时结束。如果结束时，最小生成树的边数小于总顶点数减一，说明该图不连通。

下面是Kruskal算法的Python代码实现：

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

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskal(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 and i < len(self.graph):
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)

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

        return result

2. Prim算法

Prim算法也是一种基于贪心策略的算法，它的基本思想是从一个顶点开始，每次选择一个与当前生成树相邻的权值最小的顶点加入到生成树中，直到生成树中的边数等于总顶点数减一或者测试完所有边时结束。如果结束时，最小生成树的边数小于总顶点数减一，说明该图不连通。

下面是Prim算法的Python代码实现：

import sys

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

    def print_mst(self, parent):
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

    def min_key(self, key, mst_set):
        min = sys.maxsize
        for v in range(self.V):
            if key[v] < min and mst_set[v] == False:
                min = key[v]
                min_index = v
        return min_index

    def prim(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        mst_set = [False] * self.V
        parent[0] = -1

        for cout in range(self.V):
            u = self.min_key(key, mst_set)
            mst_set[u] = True

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

        self.print_mst(parent)