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

최소 스패닝 트리란 스패닝 트리중 모든 가중치의 합이 최소인 트리이다. (프림, 크루스칼) 

 

1. 크루스칼 알고리즘 

- 가중치가 최소인 간선을 하나씩 선택해 나가는 간선 기반 알고리즘이다.  사이클이 발생하는 경우에 대해서는 예외 처리가 필요하다. 

def find_parent(a): # 부모찾기
    if parent[a] == a:
        return a
    else:
        parent[a] = find_parent(parent[a])
        return parent[a]


def merge(a, b):
    x = find_parent(a)
    y = find_parent(b)
    if x != y:
        parent[x] = y
        return True
    return False


v, e = map(int, input().split())
parent = defaultdict(int)
for i in range(1, v + 1):
    parent[i] = i

graph = []
for _ in range(e):
    graph.append(list(map(int, input().split())))
graph.sort(key=lambda x: x[2])
total = 0
for u, v, w in graph:
    if merge(u, v):
        total += w
print(total)

2. 프림 알고리즘 

-정점을 하나 선택한 후, 정점에 연결된 간선중 가장 가중칠가 작은 간선을 선택해서 연결해 나가는 정점 기반 알고리즘이다. 

 정점을 하나씩 선택해나가기 때문에 사이클은 자동으로 고려가 된다. (visit) 

def prim(tree,start):
    queue = []
    visit = defaultdict(lambda : False)
    heapq.heappush(queue,(0,start)) # 비용, 노드 
    sum = 0 

    while queue:
        weight, node = heapq.heappop(queue)
        if visit[node]: #큐에 같은 노드가 여러번 들어가있을 수 있으므로 한번 더 체크 필수
            continue
        else :
            visit[node] = True
            sum += weight
        
        for nextV in tree[node]: # 다음노드, 비용 
            if not visit[nextV[0]]:
                heapq.heappush(queue,(nextV[1],nextV[0]))
    return sum 

 

3. 다익스트라 알고리즘 (최단 경로 알고리즘)

-하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는 알고리즘이다. 

def dijkstra(edges,K):
    queue = []
    distance = defaultdict(lambda :INF)
    found = defaultdict(lambda : False)
    heapq.heappush(queue,(0,K))
    distance[K]= 0

    while queue:
        v = heapq.heappop(queue)
        found[v[1]] = True
        for nextV in edges[v[1]]:
            node = nextV[0]
            cost = nextV[1]
            if distance[v[1]]+cost < distance[node] and not found[node]:
                distance[node]= distance[v[1]] + cost
                heapq.heappush(queue,(distance[node],node))
    return distance

프림과 다익스트라 알고리즘이 처음엔 헷갈렸었는데 가장 큰 차이라고 하면 다익스트라는 모든 정점과 정점이 최소 가중치로 연결이 되어있지만 프림은 아닐 수 있다는 것이다. 또한 프림은 무방향 그래프에서만 사용이 가능하다. 다익스트라는 모든 정점을 탐색할 필요가 없다.