Kim Jisong

I am an amazing person.

스패닝트리 Kruskal

Introduction

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있다.

  • 간선을 거리가 짧은 순서대로 그래프에 포함시키는 것으로 해결
  • 사이클이 발생하면 안 되기 때문에 사이클을 형성하는 경우 간선을 포함하지 않는다
    • Union-Find 알고리즘 사용
    • Union-Find에서 부모 노드가 하나가 되도록 하게 함

실행순서

  1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
  2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
    • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
    • 루트 노드가 서로 다르다면 두 노드에 대하여 union연산을 수행한다. * 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
    • 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
  3. 모든 간선에 대해서 2번의 과정을 반복한다.
import sys
input = sys.stdin.readline

V, E = map(int,input().split())

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
#   -> 독립된 노드라는 의미
parent = [0]*(V+1)
for i in range(1,V+1):
    parent[i] = i

# 간선을 입력받아 cost를 기준으로 오름차순 정렬
edges = []
for _ in range(E):
    A, B, C = map(int,input().split())
    edges.append((C,A,B))
edges.sort()

## Union-Find Algorithm
# Find: 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
# Union: 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

result = 0
## Kruskal Algorithm
# cost가 낮은 순으로 정렬된 간선을 하나씩 확인
for edge in edges:
    cost, a, b = edge
    # 두 노드의 루트 노드가 서로 다르면 사이클이 발생하지 않는다.
    if find_parent(parent,a) != find_parent(parent,b):
        # 신장 트리 추가 및 사이클 태이블 갱신
        union_parent(parent,a,b)
        result += cost

print(result)

2022

Stack

less than 1 minute read

Introduction

Stack

less than 1 minute read

Introduction

Download-only-one-directory

less than 1 minute read

Git 명령어를 사용한 하위 디렉토리 다운로드 Clone 할 로컬 저장소 생성

Sort

3 minute read

Introduction

Tree

less than 1 minute read

Introduction

Mutex library on C++

less than 1 minute read

#include <iostream> #include <thread> #include <chrono> #include <mutex> #include <atomic> #include <string.h>

TODO

less than 1 minute read

how to costom github blog using jekyll

Welcome to Jekyll!

less than 1 minute read

You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different wa...

Back to top ↑