【代码随想录算法训练营第六十二天|卡码网53.寻宝（prim算法和kruskal算法）】

53.寻宝

prim算法

prim算法三部曲：
1.选择当前最短入树结点；2.更新入树结点；3.更新结点距离最小生成树的距离。
可以把所有已经使用过的结点看作一个整体，然后把他们相接的结点的结点顶点边中进行选择，选择最短的一条边把该结点入树，某种程度来说也是一种贪心？

V, E = map(int, input().split())
nodes = [[float('inf')] * (V+1) for _ in range(V+1)]
for i in range(E):
    start, end, length = map(int, input().split())
    nodes[start][end] = length
    nodes[end][start] = length

visited = [False] * (V+1)
minDist = [float('inf')] * (V+1)

cur = 1 
for i in range(V-1):
    minD = float('inf')
    # 1.选择最短入树结点
    for j in range(1, V+1):
        if not visited[j] and minDist[j]<minD:
            cur = j
            minD = minDist[j]
    # 2.入树
    visited[cur] = True
    # 3.更新相接不在树中的顶点的距离
    for i in range(1, V+1):
        if not visited[i] and nodes[cur][i] < minDist[i]:
            minDist[i] = nodes[cur][i]
result = 0
for i in range(2, V+1):
    result += minDist[i]
print(result)
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

kruskal算法

kruskal算法以边为导向，先把边按照长度从小到大排序，然后一个个检查边的两个端点是否在同一个集合中（这里使用并查集判断），在同一个集合中就不加入这个边，不在的话就加入。

V, E = map(int, input().split())
edges = []
for i in range(E):
    edges.append(list(map(int, input().split())))
edges.sort(key= lambda edge: edge[2])

father = [0] * (V+1)
for i in range(V+1):
    father[i] = i

def find(u):
    if father[u] != u:
        father[u] = find(father[u])
    return father[u]

def isSame(u, v):
    u = find(u)
    v = find(v)
    return u == v

def join(u, v):
    u = find(u)
    v = find(v)
    if not u==v:
        father[v] = u

result = 0
for edge in edges:
    start = edge[0]
    end = edge[1]
    val = edge[2]
    if not isSame(start, end):
        result += val
        join(start, end)
print(result)
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
32
33
34
35