[For competition professionals] Minimum spanning tree summary

Method to find the minimum spanning tree

Use properly

Was in discussion https://togetter.com/li/776049

Do you use it properly according to the input format?

https://www.hamayanhamayan.com/entry/2018/09/17/163004

Prim's algorithm

  1. Start from any starting point.
  2. Select and connect the nodes that can be moved at the lowest cost.
  3. Repeat 2 and when all the nodes are connected, it becomes the minimum spanning tree.

What should I do

Every time you connect a node, the options expand, and you always want to select the smallest one. → Use priority queue (heapq).

When a tuple is passed to heapq, the minimum value is determined by the first element.

What is good

O(ElogV)。 Is it faster with the Fibonacci heap?

image

https://algo-logic.info/prim-mst/

Example of use

AOJ ALDS1_12_A

Prim's algorithm


import heapq

def main():
    n = int(input())
    next = []   #Adjacency management list
    for _ in range(n):
        l = list(map(int, input().split()))
        next.append([(c, i) for i, c in enumerate(l) if c != -1])
    visited = [0] * n
    connection = 0
    q = [(0, 0)]    # (cost, v)
    heapq.heapify(q)
    ans = 0
    while len(q):
        cost, v = heapq.heappop(q)
        if visited[v]:
            continue

        #Connect with that node
        visited[v] = 1
        connection += 1
        ans += cost
        
        #Enqueue where you can go from the newly connected node
        for i in next[v]:
            heapq.heappush(q, i)
        
        #Exit when all nodes are connected
        if connection == n:
            break
    print(ans)
    return

Kruskal method

  1. Select all sides in ascending order of weight.
  2. Discard anything that creates a cycle in the process. Do this for all sides.
  3. Only the finally selected side becomes the minimum spanning tree.

What should I do

1 → Sort based on the cost of the edge. Use the technique of sorting by the first element when each element of the list is made into a tuple and sorted. 2 → "A cycle can be closed" = "Make a side where two points are already connected", so check with the Union Find tree.

What is good

O(ElogV)。

image

https://algo-logic.info/kruskal-mst/

Example of use

AOJ GRL_2_A

Kruskal method


def main():
    V, E = map(int, input().split())
    uf = UnionFind(V)

    #Process of 1
    edges = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        edges.append((w, s, t))
    edges.sort()

    #Process 2
    cost = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            cost += w
            uf.union(s, t)
    print(cost)
    return

Postscript (6/1)

Thinking

Application example

ARC076 D - Built? First: Consider reducing E in advance if it is huge. → This time, we used that towns that are not adjacent to each other on the x-coordinate and the y-coordinate cannot be selected. Second: If both the x-axis and y-axis correspond to adjacent towns, they are counted twice, but I don't care.

def main():
    N = int(input())
    nodes = []
    for i in range(N):
        x, y = map(int, input().split())
        nodes.append((x, y, i))  #If the coordinates are unique, the tuples will be put into Union Find, but since there are cases where there are towns at the same coordinates, number them.

    uf = UnionFind(N)
    nodes_sorted_by_x = sorted(nodes)
    nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])

    edges = []
    for i in range(N - 1):
        dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
        dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_x[i][2],  nodes_sorted_by_x[i + 1][2]))

    for i in range(N - 1):
        dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
        dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_y[i][2],  nodes_sorted_by_y[i + 1][2]))

    edges.sort()
        
    ans = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            ans += w
            uf.union(s, t)
    print(ans)

Appendix

Specifies the key for sorting the list of tuples.

#Usually sorted by the first element of the tuple.
sortedByFirstKey  = sorted(listOfTuple)
#Specify a lambda expression for Key and sort by the second element of the tuple.
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1])
# reverse
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1], reverse=True)

Especially when trying to sort the list of dictionaries, an error will occur, so it is necessary to specify key as described above. Specify the reverse order with reverse. Can be used with either sort () or sorted ().


reference

Recommended Posts

[For competition professionals] Minimum spanning tree summary
[For competition professionals] Union Find Tree Summary
Binary search summary for competition professionals
[For competition professionals] Run-length compression summary
[For competition professionals] Summary of doubling
[For competition professionals] Prime number, divisor, prime factorization summary
Minimum spanning tree in C #
[For competition pros] Priority queue (heapq) Summary
Summary for learning RAPIDS