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] = w
        graph[y][x] = w
    
    visited = [False] * (v+1)
    minDis = [10001] * (v+1)
    
    for i in range(1, v+1):
        min_Val = 10002
        cur = -1

        # step 1
        for j in range(1, v+1):
            if visited[j] == False and minDis[j] < min_Val:
                cur = j
                min_Val = minDis[j]

        # step 2
        visited[cur] = True

        # step 3
        for k in range(1, v+1):
            if visited[k] == False and minDis[k] > graph[cur][k]:
                minDis[k] = graph[cur][k]
                
    res = 0
    for i in range(2, v+1):
        res += minDis[i]
    
    print(res)
    
    return

if __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 = l
        self.r = r
        self.weight = weight

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

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

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

def 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 = 0
    for i in range(e):
        if not isSame(edges[i].l, edges[i].r, father):
            result += edges[i].weight
            join(edges[i].l, edges[i].r, father)
    
    print(result)
    
    return

if __name__ == "__main__":
    main()