Tree, Graph
트리
계층형 관계를 표현가능한 자료구조
|Edge| = |Vertex| - 1
이진트리
모든 정점의 자식 수가 최대 n개 이하인 트리를 n진 트리(n-ary tree)라고 한다.
ex) n=2이면, 이진트리이다.
완전 이진 트리
- 트리의 마지막 레벨을 제외한 나머지 레벨에서는 정점이 완전히 채워져 있어야 한다.
- 트리의 마지막 레벨에 있는 노드는 왼쪽에서부터 오른쪽으로 순서대로 채워져 있어야 한다.
그래프 표현 방법
인접 행렬
N * N 크기를 갖는 2차원 배열로 관리한다.
1 <= i, j <= N에 대하여 간선 (i, j)가 존재하면, E[i][j] = 1 간선 (i, j)가 존재하지 않으면, E[i][j] = 0 과 같이 정의한다.
장점
- 정점 두개가 주어지면, 두 정점을 잊는 간선이 존재하는지 O(1)에 판별할 수 있다.
- 그래프가 빽빽할 때 유리하다.
단점
- 간선의 수와 관계없이 항상 O(N^2)의 공간 복잡도가 필요하다.
- 어떤 정점 하나와 인접한 정점의 목록을 보는데 항상 O(N)의 시간이 걸린다. 모든 정점에 대해 이 작업을 반복하면 O(N^2)의 시간이 걸린다.
인접 리스트
각 정점에 대하여 인접한 정점의 목록만 저장한다.
1 <= i, j <= N에 대하여 E[i] = {j | 간선 (i, j)가 존재하면} 로 같이 정의한다.
즉, 특정 정점과 인접한 정점의 목록만 저장한다.
장점
- 간선의 수와 비례하여 자료를 저장하므로, 간선의 수가 적으면 인접 행렬보다 적은 공간이 필요하다.
- 각 정점에 대하여 인접한 정점을 보는 작업이 쉽다. 모든 정점에 대하여 이 작업을 반복하면 O(|E|)의 시간만 필요로 한다.
단점
- 정점 두 개가 주어졌을 때, 두 정점이 인접하는지 판별하는 것이 어렵다.
그래프 탐색
그래프 내의 모든 정점들을 한번씩 방문하는 과정으로
어떤 정점에서 시작해, 간선을 따라 방문할 수 있는 모든 정점을 방문한다.
정점을 방문하는 순서에 따라 크게 2가지인 DFS, BFS로 나뉜다.
DFS (Depth First Search)
깊이가 깊어지는 방향으로 그래프를 탐색한다.
현재 방문해 있는 정점과 인접한 정점 중
- 아직 방문하지 않은 정점이 있다면, 해당 정점을 방문한다.
- 방문하지 않은 정점이 없다면, 직전 방문했던 정점으로 돌아간다.
구현
주로 재귀함수를 이용한다.
각 노드가 연결된 정보를 2차원 리스트 자료형을 표현하였다.
visited = [False * 9]
def dfs(graph, v, visited):
visited[v] = True # 현재 노드를 방문 처리
print(v, end=' ')
# 현재 노드와 연결된 다른 노드들을 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)시간복잡도는 O(V+E)이다.
sys.setrecursionlimit()을 사용하면 Python이 정한 최대 재귀 깊이를 변경할 수 있다.
ex)sys.setrecursionlimit(10**6)
BFS (Breath First Search)
한 정점에서 인접한 정점들을 전부 방문하여 그래프를 탐색
- 시작 정점을 queue에 push
queue가 빌 때까지 다음 과정을 반복
- front 정점과 인접한 정점들 중,
방문하지 않은 정점들을 방문처리 & queue에 push - front 정점을 pop
구현
주로 큐를 이용한다.
from collections import deque
visited = [False * 9]
def bfs(graph, start, visited):
queue = deque([start]) # 큐 구현을 위해 deque 라이브러리 사용
visited[start] = True # 현재 노드를 방문 처리
# 큐가 빌 때까지 반복
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True시간복잡도는 O(V+E)이다.
