Prim算法与Kruskal算法在Python中的比较分析

2023-04-17 00:00:00 分析算法 Prim

Prim算法和Kruskal算法都是解决最小生成树问题的经典算法，它们的基本思想是不同的。

Prim算法是一种贪心算法，从一个节点开始构建最小生成树，每次选择与已构建部分最近的节点，直到所有节点都被加入到生成树中。具体步骤如下：

1.随机选一个节点作为起始点，加入到生成树中。
2.对于一个已加入生成树的节点，选择离它最近的未加入节点加入到生成树中。
3.重复步骤2，直到所有节点都被加入到生成树中。

Kruskal算法也是一种贪心算法，从边集开始构建最小生成树，每次选择边权值最小的边，并保证所选边不会形成环，直到所有节点都被加入到生成树中。具体步骤如下：

1.将边集按权值从小到大排序。
2.从权值最小的边开始，判断所选边的两个端点是否在同一棵树中，若不在同一棵树中，则将所选边加入到生成树中。
3.重复步骤2，直到所有节点都被加入到生成树中。

在实际应用中，两种算法各有优劣，根据具体情况选择不同的算法可以获得更高效的结果。一般来说，如果节点数比较小，那么Prim算法执行效率更高；如果节点数比较大，那么Kruskal算法更优。

下面是Python代码演示，以字符串为例：

Prim算法：

import heapq

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = [[0] * vertices for i in range(vertices)]

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

    def prim_mst(self):
        visited = [False] * self.vertices
        pq = []
        heapq.heappush(pq, (0, 0))
        mst = [None] * self.vertices
        mst[0] = -1
        while pq:
            weight, index = heapq.heappop(pq)
            visited[index] = True
            for i in range(self.vertices):
                if self.graph[index][i] != 0 and not visited[i]:
                    heapq.heappush(pq, (self.graph[index][i], i))
                    mst[i] = index
        for i in range(1, self.vertices):
            print("Edge:", i, "-", mst[i], "\tWeight:", self.graph[i][mst[i]])

g = Graph(7)
g.add_edge(0, 1, 5)
g.add_edge(0, 5, 3)
g.add_edge(1, 2, 2)
g.add_edge(1, 6, 7)
g.add_edge(2, 3, 9)
g.add_edge(3, 4, 2)
g.add_edge(4, 5, 4)
g.add_edge(5, 6, 8)
g.prim_mst()

输出结果：
Edge: 1 - 0     Weight: 5
Edge: 2 - 1     Weight: 2
Edge: 3 - 2     Weight: 9
Edge: 4 - 3     Weight: 2
Edge: 5 - 0     Weight: 3
Edge: 6 - 5     Weight: 8

Kruskal算法：

class Graph:
    def __init__(self, vertices):
        self.vertices = 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_mst(self):
        result = []
        i = 0
        e = 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []
        for node in range(self.vertices):
            parent.append(node)
            rank.append(0)
        while e < self.vertices - 1:
            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)
        for u, v, weight in result:
            print("%d - %d: %d" % (u, v, weight))

g = Graph(7)
g.add_edge(0, 1, 5)
g.add_edge(0, 5, 3)
g.add_edge(1, 2, 2)
g.add_edge(1, 6, 7)
g.add_edge(2, 3, 9)
g.add_edge(3, 4, 2)
g.add_edge(4, 5, 4)
g.add_edge(5, 6, 8)
g.kruskal_mst()

输出结果：
1 - 2: 2
3 - 4: 2
0 - 5: 3
4 - 5: 4
0 - 1: 5
5 - 6: 8

相关文章