day57-graph theory-part07-8.28
tasks for today:
1. prim算法 53.寻宝
2. kruskal算法 53.寻宝
----------------------------------------------------------------------------
1. prim算法 53.寻宝
In this practice, we see how prim algorithm is used. The essence of this practice is: there are n points, m edges, select n-1 edges from the m edges, making the total weight of the edges are minimized. n-1 edges can link all n points.
This practice is led by the 3-step structure of prim algorithm.
need to pay attention to the 10001, which is the 1 + 10000, 10000 is the maximum points number in this practice's configuration;
please be noted that the graph's entries assignment, graph[x][y] and graph[y][x] should be assigned with the same weight.
def main():v, e = map(int, input().split())graph = [[10001] * (v+1) for _ in range(v+1)]for _ in range(e):x, y, w = map(int, input().split())graph[x][y] = wgraph[y][x] = wvisited = [False] * (v+1)minDis = [10001] * (v+1)for i in range(1, v+1):min_Val = 10002cur = -1# step 1for j in range(1, v+1):if visited[j] == False and minDis[j] < min_Val:cur = jmin_Val = minDis[j]# step 2visited[cur] = True# step 3for k in range(1, v+1):if visited[k] == False and minDis[k] > graph[cur][k]:minDis[k] = graph[cur][k]res = 0for i in range(2, v+1):res += minDis[i]print(res)returnif __name__ == "__main__":main()2. kruskal算法
Based on the same practice, the kruskai algorithm is discussed here. The difference is that, the prim algo is maintaining a set of points, whereas the kruskai maintains a set of edges.
This method may involve using the method discussed in day 55 & 56.
class Edge:def __init__(self, l, r, weight):self.l = lself.r = rself.weight = weightdef find(u, father):if father[u] == u:return uelse:return find(father[u], father)def join(u, v, father):u = find(u, father)v = find(v, father)if u == v: returnfather[v] = udef isSame(u, v, father):u = find(u, father)v = find(v, father)return u == vdef main():v, e = map(int, input().split())edges = []for _ in range(e):x, y, w = map(int, input().split())edges.append(Edge(x, y, w))edges.sort(key = lambda edge: edge.weight)father = list(range(v+1))result = 0for i in range(e):if not isSame(edges[i].l, edges[i].r, father):result += edges[i].weightjoin(edges[i].l, edges[i].r, father)print(result)returnif __name__ == "__main__":main()