반응형
신장 트리
- 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다
- 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다
최소 신장 트리
- 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야 할까?
- 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게
도로를 설치하는 경우를 생각해 보자- 두 도시 A,B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치한다
크루스칼 알고리즘
- 대표적인 최소 신장 트리 알고리즘이다
- 그리디 알고리즘으로 분류된다
- 구체적인 동작 과정은 다음과 같다
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다
- 모든 간선에 대하여 2번의 과정을 반복한다
크루스칼 알고리즘: 동작 과정 살펴보기
- [초기 단계] 그래프의 모든 간선 정보에 대하여 오름차순 정렬을 수행한다
- [Step 1] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (3,4)를 선택하여 처리한다
- [Step 2] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (4,7)을 선택하여 처리한다
- [Step 3] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (4,6)을 선택하여 처리한다
- [Step 4] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (6,7)을 선택하여 처리한다
- [Step 5] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (1,2)를 선택하여 처리한다
- [Step 6] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (2,6)을 선택하여 처리한다
- [Step 7] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (2,3)을 선택하여 처리한다
- [Step 8] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (5,6)을 선택하여 처리한다
- [Step 9] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (1,5)를 선택하여 처리한다
- [알고리즘 수행 결과]
- 최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당한다
크루스칼 알고리즘 (Python)
#특정 원소가 속한 집합 찾기
def find_parent(parent, x):
#루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x]!=x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
#두 원소가 속한 집합을 합치기
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
#노드의 개수, 간선의 개수 입력받기
v, e=map(int, input().split())
parent=[0]*(v+1) #부모테이블 초기화
#모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges=[]
result=0
# 부모 테이블상에서, 부모를 자기자신으로 초기화
for i in range(1, v+1):
parent[i] = i
#모든 간선에 대한 정보를 입력 받기
for _ in range(e):
a,b,cost=map(int, input().split())
#비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.append((cost,a,b))
#간선을 비용순으로 정렬
edges.sort()
#간선을 하나씩 확인하며
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)
크루스칼 알고리즘 성능 분석
- 크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE) 의 시간 복잡도를 가진다
- 크루스칼 알고리즘에서 가장 많은 시간을 요구하는 곳은 간선의 정렬을 수행하는 부분이다
- 표준 라이브러리를 이용해 𝐸개의 데이터를 정렬하기 위한 시간 복잡도는 O(ElogE) 이다
위상 정렬
- 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미
- 예시) 선수과목을 고려한 학습 순서 설정
- 위 세 과목을 모두 듣기 위한 적절한 학습 순서는?
- 자료구조 → 알고리즘 → 고급 알고리즘 (O)
- 자료구조 → 고급 알고리즘 → 알고리즘 (X)
진입차수와 진출차수
- 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
- 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수
위상 정렬 알고리즘
- 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다
- 진입차수가 0인 모든 노드를 큐에 넣는다
- 큐가 빌 때까지 다음의 과정을 반복한다
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다
=> 결과 적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다
위상 정렬 동작 예시
- 위상 정렬을 수행할 그래프를 준비한다
- 이때 그래프는 사이클이 없는 방향 그래프 (DAG)여야 한다
- [초기 단계] 초기 단계에서는 진입차수가 0인 모든 노드를 큐에 넣는다
- 처음에 노드 1이 큐에 삽입된다
- [Step 1] 큐에서 노드 1을 꺼낸 뒤에 노드 1에서 나가는 간선을 제거한다
- 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다
- [Step 2] 큐에서 노드 2를 꺼낸 뒤에 노드 2에서 나가는 간선을 제거한다
- 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다
- [Step 3] 큐에서 노드 5를 꺼낸 뒤에 노드 5에서 나가는 간선을 제거한다
- 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다
- [Step 4] 큐에서 노드 3를 꺼낸 뒤에 노드 3에서 나가는 간선을 제거한다
- 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다
- [Step 5] 큐에서 노드 6을 꺼낸 뒤에 노드 6에서 나가는 간선을 제거한다
- 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다
- [Step 6] 큐에서 노드 4를 꺼낸 뒤에 노드 4에서 나가는 간선을 제거한다
- 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다
- [Step 7] 큐에서 노드 7을 꺼낸 뒤에 노드 7에서 나가는 간선을 제거한다
- 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다
- [위상 정렬 결과]
- 큐에 삽입된 전체 노드 순서: 1 → 2 → 5 → 3 → 6 → 4 → 7
위상 정렬의 특징
- 위상 정렬은 DAG에 대해서만 수행할 수 있다
- DAG (Direct Acyclic Graph): 순환하지 않는 방향 그래프
- 위상 정렬에서는 여러 가지 답이 존재할 수 있다
- 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재한다
- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다
- 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못한다
- 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다
위상 정렬 알고리즘 (Python)
import collections import deque
#노드의 개수와 간선의 개수를 입력받기
v, e = map(int, input().split())
#모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0]*(v+1)
#각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v+1)]
#방향그래프의 모든 간선 정보를 입력받기
for _ in range(e):
a,b = map(int, input().split())
graph[a].append(b) #정넘 a에서 b로 이동가능
#진입차수를 1 증가
indegree[b]+=1
#위상 정렬 함수
def topology_sort():
result = [] #알고리즘 수행 결과를 담을 리스트
q=deque() #큐 기능을 위한 deque 라이브러리 사용
#처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
#큐가 빌 때까지 반복
while q:
#큐에서 원소 꺼내기
now = q.popleft()
result.append(now)
#해당 원소와 연결된 노드들의 진입차수에서 1빼기
for i in graph[now]:
indegree[i] -=1
#새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
#위상 정렬을 수행한 결과 출력
for i in result:
print(i, end = " ")
topology_sort()
입력 예시
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
출력 예시
1 2 5 3 6 4 7
위상 정렬 알고리즘 성능 분석
- 위상 정렬을 위해 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차레대로 제거해야 한다
- 위상 정렬 알고리즘의 시간 복잡도는 O(V + E) 이다
'코딩 > 알고리즘' 카테고리의 다른 글
[이코테]4장_DFS, BFS (0) | 2024.03.08 |
---|---|
[이코테]10장(3)_기타(소수판별, 에라토스테네스의 체) (6) | 2024.03.08 |
[이코테]10장_그래프이론(1)서로소집합 (3) | 2024.03.07 |
[이코테]9장_최단 경로 알고리즘 문풀 (1) | 2024.03.07 |
[이코테]9장_다익스트라 알고리즘, 플로이드 워셜 알고리즘 (2) | 2024.03.07 |