1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import sys

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

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        mstSet = [False] * self.V

        for _ in range(self.V):
            u = min((key[v], v) for v in range(self.V) if not mstSet[v])[1]
            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], parent[v] = self.graph[u][v], u

        for i in range(1, self.V):
            print(f"{parent[i]} - {i}: {self.graph[i][parent[i]]}")

# 示例
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()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

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

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

    def kruskalMST(self):
        self.graph.sort(key=lambda x: x[2])
        parent, rank = list(range(self.V)), [0] * self.V
        result = []

        for u, v, w in self.graph:
            x, y = self.find(parent, u), self.find(parent, v)
            if x != y:
                result.append([u, v, w])
                parent[y] = x if rank[x] > rank[y] else y
                if rank[x] == rank[y]:
                    rank[x if parent[y] == x else y] += 1

        for u, v, w in result:
            print(f"{u} - {v}: {w}")

# 示例
g = Graph(4)
g.addEdge(0,1,10), g.addEdge(0,2,6), g.addEdge(0,3,5), g.addEdge(1,3,15), g.addEdge(2,3,4)
g.kruskalMST()