그래프 탐색 기본
그래프(Graph)
그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 그래프의 종류는 다음과 같다.
- 무방향 그래프 : 간선이 방향을 가지지 않음
- 방향 그래프 : 간선이 방향을 가지고 있음
- 가중치 그래프 : 각 간선에 가중치 정보가 포함됨. 가중치는 거리, 비용 등으로 표현할 수 있다.
- 연결 그래프 : 무방향 그래프에서 특정 정점 쌍 사이에 경로가 존재하지 않는 경우
- 비연결 그래프 : 무방향 그래프에서 특정 정점 쌍 사이에 경로가 존재하지 않는 경우
- 순환 그래프 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
- 비순환 그래프 : 사이클이 없는 그래프
- 완전 그래프 : 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
그래프와 관련된 용어
- 정점(Vertex) : 노드(node) 라고도 하며 정점에는 데이터가 저장된다.
- 간선(Edge) : 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다.
- 인접 정점(adjacent Vertex) : 간선에 의해 직접 연결된 정점
- 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우. 한붓그리기와 같이 같은 간선을 지나가지 않는 경로
- 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진출 차수(in-degree) : 방향 그래프에서 외부로 향하는 간선의 수
- 진입 차수(out-degree) : 방향 그래프에서 외부에서 들어오는 간선의 수
- 경로 길이(path length) : 경로를 구성하는데 사용된 간선의 수
- 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
이진 탐색 트리
이진 트리는 최대 두 개의 자식(없을 수 있다)을 가지는 트리 형태의 자료구조이다. 탐색을 하거나 정렬을 하는데 있어 매우 효율적으로 사용된다. 탐색의 시간복잡도는 평균적으로 O(lognN)이다.
이진 탐색 트리는 이진 트리의 하나이다. 노드에 대해서 왼쪽 자식의 값은 노드의 값보다 작거나 같고, 오른쪽 자식은 노드의 값보다 크다. 아래의 그림을 보면 [21, 28, 14, 32, 25, 18, 11, 30, 19, 15]의 순서대로 이진 탐색 트리를 구현하는 과정을 나타내고 있다. 가장 처음의 값은 root 노드가 되고, 다음 값부터 노드와의 대소 비교관계에 따라 위치를 결정한다.
아래의 그림을 보면 위에서 구현한 이진 탐색 트리에서 27을 찾는 과정을 나타낸다. 이진 탐색 트리는 그 밑에 보이는 정렬된 리스트보다 더 효율적으로 원하는 값을 찾을 수 있다.
유니온 파인드 알고리즘
# 특정 원소가 속한 집합을 찾기
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
# 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=' ')크루스 칼 알고리즘
# 특정 원소가 속한 집합을 찾기
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)그래프 탐색 기본 관련 백준 문제 Github 링크
백준 그래프 탐색 기본 관련 문제
: )