크루스칼, 프림, 다익스트라

정리 하는중

최소 신장 트리

모든 노드를 이었을때 간선의 가중치의 합이 최소인 트리

 

크루스칼

from heapq import heappop, heappush

def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x])
    return parent[x]

def union(x,y):
    x,y=find(x),find(y)
    parent[x]=y

def kruskal():
    cost=0
    
    while q:
        dist, v1, v2 = heappop(q)
        if find(v1) == find(v2):
            continue
        else:
            cost += dist
            union(v1, v2)
    return cost

if __name__=="__main__":
    N = int(input())
    M = int(input())
    q=[]
    for _ in range(M):
        a, b, c = map(int, input().split())
        heappush(q, [c, b, a])
    
    parent = [i for i in range(N+1)]
    

 

프림

from heapq import heappop, heappush

def prim():
    visited=[False]*(N+1)
    q=[]
    heappush(q, [0, 1])
    ret=0

    while q:
        dist, curr=heappop(q)
        if visited[curr]:continue
        visited[curr]=True
        ret+=dist

        for next_c, next_node in graph[curr]:
            heappush(q, ([next_c, next_node]))

    return ret




if __name__=="__main__":
    N=int(input())
    M=int(input())
    graph=[[] for _ in range(N+1)]

    for _ in range(M):
        a, b, c = map(int, input().split())

        if a==b : continue

        graph[a].append([c, b])
        graph[b].append([c, a])
    print(prim())

 

다익스트라

from heapq import heappop, heappush

def dijkstra(start, target):
    q = []
    distance=[10**9]*(N+1)
    distance[start]=0
    heappush(q, [0, start])

    while q:
        dist, curr = heappop(q)
        if distance[curr]<dist:
            continue

        for next_c, next_node in graph[curr]:
            cost=dist+next_c
            if cost<distance[next_node]:
                distance[next_node]=cost
                heappush(q, ([cost, next_node]))

    return distance[target]




if __name__=="__main__":
    N=int(input())
    M=int(input())
    graph=[[] for _ in range(N+1)]

    for _ in range(M):
        a, b, c = map(int, input().split())

        if a==b : continue

        graph[a].append([c, b])

    start, target = map(int, input().split())
    print(dijkstra(start, target))

 

 

https://www.acmicpc.net/problem/1922

https://www.acmicpc.net/problem/1916