Graph

서로 다른 개체가 연결되어 있다 --> 그래프 알고리즘 떠올릴 것

 

최소 힙 : 트리 자료구조에 속함. 계층적인 모델

 

서로소 집합 Disjoint Sets

- 서로소 집합 자료구조

--> union-fine 자료구조라고 불리기도 함

- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

- 트리 자료구조를 이용해서 집합을 표현

- union과 find 2개의 연산으로 조작 가능

union 

2개의 원소가 포함된 집합을 하나의 집합으로 합침

find 

특정한 원소가 속한 집합이 어떤 집합인지 알려줌

트리 자료구조를 이용해서 집합 표현하는 서로소 집합 계산 알고리즘

1. union을 확인해서 서로 연결된 두 노드 A, B를 확인

1) A와 B의 루트 노드 A', B'를 각각 찾음

2) A'를 B'의 부모노드로 설정

2. 모든 union 연산을 처리할 때까지 1번 과정 반복

 

* union 연산을 토대로 그래프를 그리면 '연결성'으로 손쉽게 집합의 형태 확인 가능함

* union 연산을 효과적으로 수행하기 위해서는 '부모 테이블'을 항상 가지고 있어야 함

# 특정 원소가 속한 집합 찾기
def fine_parent(parent, x):
    # 루트 노드가 아니면 루트 노드 찾을 때까지 재귀적으로 호출
    if parent[x]!=x:
        return fine_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합 합치기
def union_parent(parent, a,b):
    a=fine_parent(parent, a)
    b=fine_parent(parent, b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

# 노드의 개수와 union 연산의 개수 입력받기
v,e=map(int, input().split())
parent=[0]*(v+1) # 부모 테이블 초기화

# 부모 테이블상에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i]=i

# union 연산 각각 수행
for i in range(e):
    a,b=map(int, input().split())
    union_parent(parent, a,b)

 

신장 트리 Spanning Tree

: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

* 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않음

 

크루스칼 알고리즘 Kruskal Algorithm

신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘 중 대표격

가장 적은 비용으로 모든 노드 연결 가능

그리디 알고리즘으로 분류됨

최종적으로 신장 트리에 포함되는 간선 갯수는 '노드의 갯수 -1'

알고리즘

1. 간선 데이터를 비용에 따라 오름차순으로 정렬

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인

1) 사이클이 발생하지 않으면 최소 신장 트리에 포함

2) 사이클이 발생하는 경우 최소 신장 트리에 포함

3. 모든 간선에 대해 2번 과정 반복

 

위상 정렬 Topology Sort

방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

진입차수 Indegree

특정한 노드로 '들어오는' 간선의 개수를 의미

위상 정렬 알고리즘

1. 진입차수가 0인 노드를 큐에 넣음

2. 큐가 빌 때까지 다음 과정 반복

1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거

2) 새롭게 진입차수가 0이 된 노드를 큐에 넣음