트리 : 정점과 선분을 이용하여 사이클을 이루지 않도록 구성한
그래프의 특수한 형태
트리 관련 용어
운행법(Traversal) : 트리를 구성하는 각 노드들을 찾아가는 방법
이진 트리의 운행법 (Root 위치 확인하기)
산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리
를 많이 사용한다. 이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위, 전위, 후위 표기법이 된다.
그래프 : 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조
그래프 | 트리 | |
---|---|---|
방향성 | 방향 그래프 혹은 무방향 그래프 | 방향 그래프 |
순환성 | 순환 및 비순환 | 비순환 |
루트 노드 존재 여부 | 루트 노드가 없음 | 루트 노드가 존재 |
노드간 관계성 | 부모와 자식 관계 없음 | 부모와 자식 관계 |
모델의 종류 | 네트워크 모델 | 계층 모델 |
그래프의 구현 방법 (두 방식은 메모리와 속도 측면에서 구별된다는 특징이 있음)
노드의 개수가 V, 간선의 개수가 E 인 그래프에서
노드의 개수가 적은 경우
에는 이 알고리즘 이용!노드와 간선의 개수가 많은 경우
에는 우선순위 큐와 함께 사용서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
서로소 집합 자료구조을 조작 가능하게 하는 2개의 연산
서로소 집합 계산 알고리즘
⇒ 이것이 트리를 이용해 서로소 집합을 계산하는 알고리즘
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x) :
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적 호출
if parent[x] != x :
return find_parent(parent, parent[x])
return 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
# 노드의 개수와 간선(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)
# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1) :
print(find_parent(parent, i), end=' ')
print()
# 부모 테이블 내용 출력
print('부모 테이블 : ', end='')
for i in range(1, v + 1) :
print(parent[i], end=' ')
노드의 개수가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때 경로 압축 방법을 적용한 시간 복잡도는 O(V+M(1+log2-M/VV))
무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있음
사이클 판별 알고리즘
# 특정 원소가 속한 집합을 찾기
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
# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1) :
parent[i] = i
cycle = False # 사이클 발생 여부
for i in range(e) :
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent, b) :
cycle = True
break
# 사이클이 발생하지 않았다면 합집합(union) 수행
else :
union_parent(parent, a, b)
if cycle :
print("사이클이 발생했습니다.")
else :
print("사이클이 발생하지 않았습니다.")
신장 트리(Spinning Tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미
크루스칼 알고리즘 : 최소 신장 트리 알고리즘
의 대표적인 알고리즘
최소 신장 트리 알고리즘
# 특정 원소가 속한 집합을 찾기
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
# 노드의 개수와 간선(union 연산)의 개수 입력받기
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(Elog)
의 시간 복잡도를 가짐
위상 정렬 : 방향 그래프의 모든 노드를 ‘방향성에 거스르지 않도록 순서대로 나열하는 것’
위상 정렬 알고리즘을 자세히 알기 전에, 먼저 진입차수를 알아야 함
위상 정렬 알고리즘
⇒ 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것
⇒ 사이클이 존재하는 경우, 사이클에 포함된 원소 중에서 어떤 원소도 큐에 들어가지 못하기 때문
from 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()