정점(vertex)는 노드라고도 불리며 그래프를 형성하는 기본적인 단위이다.
정점은 분할할 수 없는 객체이자 점으로 표현되는 위치, 사람, 물건 등이 될 수 있다.
간선(edge)는 정점을 잇는 선을 의미한다. 이는 관계, 경로 등이 될 수 있다.
어떠한 위치나 어떠한 사람으로부터 무언가를 통해 간다라고 했을 때, 어떠한 위치나 어떠한 사람은 정점이 되고, 무언가를 통해 간다는 간선이 된다.
관계에 대하여 하나의 방향이 존재하는 경우 이를 단방향 간선이라 하고, 왕복이 가능한 관계를 양방향 간선이라 한다.
정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 정점의 indegree라고 한다.
해당 정점에서 outdegree는 3개, indegree는 2개인 상태이다.
정점은 보통 약자로 V 또는 U라고 하며, 보통 어떤 정점으로부터 시작해서 어떤 정점까지 간다를 U → V라고 표현을 한다.
정점과 정점 사이에 드는 비용을 가중치라고 한다.
만약 1번 노드와 2번 노드까지 가는 비용이 한칸이라면, 1번 노드에서 2번 노드까지의 가중치는 한 칸이다.
트리는 자식 노드와 부모 노드로 이루어진 계층적인 구조를 가지며, 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미한다.
트리는 그래프의 일종이며 다음 특징을 가진다.
- 부모, 자식 계층 구조를 가진다. 같은 경로 상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드가 된다.
V - 1 = E의 특징을 가진다. 즉, 간선의 수는 노드 수 - 1이다.- 임의의 두 노드 사이의 경로는
유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나밖에 없다.
루트노드
가장 위에 존재하는 노드를 의미한다.
내부노드
루트노드와 리프노드 사이에 있는 노드를 의미한다.
리프노드
자식노드가 없는 노드를 의미한다.
트리의 높이와 레벨
다음 그림은 트리의 높이와 레벨을 설명한 그림이다.
- 깊이: 트리에서 깊이는 각각의 노드마다 다르며, 루트 노드에서 특정 노드까지 최단거리로 갔을 때의 거리를 의미한다.
- 높이: 트리의 높이는 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리를 의미한다.
- 레벨: 트리의 레벨은 보통 깊이와 같은 의미를 가진다.
- 서브트리: 트리 내의 하위 집합을 서브트리라고 한다. 즉, 트리 내에 있는 부분집합이다.
- 숲: 트리로 이루어진 집합을 숲이라고 한다.
각각의 노드의 자식노드 수가 2개 이하로 구성되어있는 트리를 의미하며 이를 다음과 같이 분류한다.
- 정이진 트리 (full binary tree): 자식 노드가 0 또는 2개인 이진 트리를 의미한다.
- 완전 이진 트리 (complete binary tree): 왼쪽에서부터 채워져잇는 이진 트리를 의미한다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.
- 변질 이진 트리 (degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미한다.
- 포화 이진 트리 (perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미한다.
- 균형 이진 트리 (balanced binary tree): 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리이다. map 혹은 set을 구성하는 레드블랙트리가 균형 이진트리 중 하나이다.
이진트리의 일종으로 노드의 오른쪽 하위 트리에는 노드의 값보다 큰 값이 있는 노드만 포함되고 왼쪽 하위트리에는 노드의 값보다 작은 값이 들어있는 트리를 의미한다.
해당 트리를 사용하는 경우 검색에 용이하다. 왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져있기 때문에 전체 탐색이 필요없어진다.
이러한 이진탐색트리의 시간복잡도는 균형잡히게 분포되어있는 경우 탐색, 삽입, 삭제, 수정 모두
그러나 이는 삽입 순서에 따라 달라진다. 만약 이러한 트리가 선형적인 형태를 띄는 경우가 존재할 수 있다.
즉, 이진탐색트리는 삽입순서에 따라 영향을 받는다. 그러나 트리의 노드들을 회전시키는 등의 방법을 통해 균형잡히게 만든 이진탐색트리에서 발전된 트리로는 AVL트리, 레드블랙트리 등이 존재한다.
실제 세계에서의 그래프를 컴퓨터에게 알려줄 표현방법으로는 인접행렬과 인접리스트가 있다.
인접행렬이란 그래프에서 정점과 간선의 관계를 나타내는 boolean 타입의 정사각형 행렬을 의미한다.
정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하는데, 0은 두 정점 사이의 경로가 없음을 의미하며, 1은 두 정점 사이의 경로가 있음을 의미한다.
다음 그래프를 아래와 같은 행렬로 표현하는 것을 의미한다.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 |
1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데, 이는 자기자신을 나타내는 것이며, 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기를 한다.
0 - 1이 연결되어있기 때문에 a[0][1] = 1 이 된다. 그러나 1 - 3은 연결되어있지 않기 때문에 a[1][3] = 0이 된다.
이를 코드로 표현한다면 다음과 같다.
bool a[4][4] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 0},
{1, 0, 0, 0},
};이를 기반으로 코드는 다음과 같이 구현할 수 있다.
보통은 2중 for문을 통해 i에서 j로 가는 경로가 있다면 어떠한 로직 또는 해당 정점으로부터 탐색하는 로직을 구축한다.
bool a[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (a[i][j]) {
cout << i << " to " << j << '\n';
bfs(i);
dfs(i);
}
}
}인접리스트는 그래프에서 정점과 간선의 관계를 나타내는 연결리스트를 의미한다.
다음과 같은 그래프가 존재할 때, 해당 그래프를 다음과 같이 나타낼 수 있다.
이를 코드로 나타내면 다음과 같다
vector<int> adj[V];
adj[0].push_back(1);
adj[0].push_back(2);
adj[0].push_back(3);
adj[1].push_back(0);
adj[1].push_back(2);
adj[2].push_back(0);
adj[2].push_back(1);
adj[3].push_back(0);인접행렬의 공간복잡도는
bool adj[V][V]; // 인접행렬
vector<int> adj[V]; // 인접리스트간선 하나를 찾을 때, 인접행렬의 시간복잡도는
// 인접행렬
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (a[i][j]) {
}
}
}
// 인접리스트
for (int j = 0; j < adj[i].size(); j++) {
cout << adj[i][j] << '\n';
}모든 간선을 찾을 때의 인접행렬의 시간복잡도는
따라서 그래프가 희소할 때는 인접리스트, 조밀할 때는 인접행렬이 좋다.
그래프가 희소할 때는 인접행렬이 인접리스트보다 메모리를 더 많이 써야한다. 간선이 없어서 인접행렬의 대부분의 요소가 0인데도 불구하고 해당 부분을 포함하여 2차원의 배열을 만들어야 하기 때문이다.
그래프가 조밀할 때는 인접행렬이 인접리스트보다 좋다. 모두 연결된 상태이기 때문에 메모리적 효율성은 동일해지고, 정점 i에서 정점 j까지의 간선이 있는지 확인하는 속도가 인접행렬에서 더 빠르다.
맵으로 그래프가 주어지는 형태가 존재한다.
그러한 경우에는 문제에서 주어진 맵을 받아서 해당 맵을 기준으로 탐색을 이어가야 한다.
또한, 맵은 하나의 그래프이다. 예를 들어 3 x 3 맵이고, 1은 갈 수 있는 지역이고 0은 갈 수 없는 지역이며, 4방향으로 탐색이 가능하다면 다음과 같은 그래프가 된다.
보통 이러한 맵을 기준으로 4가지 방향으로 탐색한다. 4가지 방향은 위, 아래, 오른쪽, 왼쪽으로 보통 주어진다.
어떤 y, x가 주어질 때, y, x를 중심으로 상하좌우 4가지 방향탐색은 어떻게 할까?
이는 위쪽부터 시계방향으로 탐색한다고 가정하면 -1, 0 / 0, 1 / 1, 0 / 0, -1을 더해가며 탐색하게 된다.
이를 배열로 나타내면 이러한 방향벡터를 정의할 수 있고 이를 기반으로 탐색한다면 다음과 같은 코드가 정의된다.
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
}연결된 컴포넌트는 연결된 하위그래프를 말하며, 연결된 하나의 덩어리라고 할 수 있다. 이 덩어리는 연결된 컴포넌트에 속한 모든 정점을 연결하는 경로가 있다라는 특징을 가진다.
위의 그림에서 연결된 컴포넌트의 수는 총 3개이고, 각각의 컴포넌트는 2개, 3개, 2개의 정점을 가진다.
다음과 같이 연결되어있는지 아니면 연결되어있지 않은지를 토대로 연결된 컴포넌트를 나눈다. 이러한 컴포넌트들을 번호를 붙여가며 색칠하는 알고리즘을 floodfill이라고 한다.
DFS는 그래프를 탐색할 때 사용하는 알고리즘이며, 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며, 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘이다.
이러한 DFS의 수도코드는 다음과 같다.
DFS(u, adj)
u.visited = true
for each v in adj[y]
if v.visited == false
DFS(v, adj)어떠한 정점 u의 visited를 참으로 바꾸고 u로부터 연결되어있는 v지점을 탐색한다.
이 때, 방문되어있지 않은 노드에 대해 재귀적으로 DFS를 호출한다.
DFS를 구현하는 방법에는 크게 2가지가 있다.
- 방문이 안된곳만 방문하기
void dfs(int here) {
visited[here] = 1;
for (int there : adj[here] {
if (visited[there]) continue;
dfs(there);
}
}방문처리는 다음과 같이 작성해도 된다.
void dfs(int here) {
for (int there : adj[here] {
if (visited[there]) continue;
visited[there] = 1;
dfs(there);
}
}아래의 코드를 사용할 경우 반드시 시작지점에 대한 방문처리를 해줘야 한다.
- 모두 방문해보기
void dfs(int here) {
if (visited[here]) return;
visited[here] = 1;
for (int there : adj[here]) {
dfs(there);
}
}무조건 dfs 함수를 호출하고, 해당 함수에서 방문되어있다면 return을 통해 함수를 종료시키는 방법이다.
BFS는 그래프를 탐색하는 알고리즘이며, 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기 전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘이다. 같은 가중치를 가진 그래프에서 최단거리알고리즘으로 사용된다.
BFS로 탐색한다는 것은 레이어별, 레벨별로 탐색한다는 의미이다.
이러한 BFS의 수도코드는 다음과 같다.
BFS(G, u)
u.visited = true
q.push(u)
while(q.size())
u = q.front()
q.pop()
for each v in G.adj[u]
if v.visited == false
v.visited = true
q.push(v)시작지점인 u에 대해 방문처리를 진행하고 큐에 push한다. 그리고 q.size()만큼 while 반복문을 돌면서 큐 앞단에 있는 u를 꺼내 해당 u를 중심으로 인접한 노드들을 탐색한다. 방문한 정점은 다시 방문하지 않고 방문처리를 하면서 큐에 push 하며 진행한다.
위의 코드는 방문처리만을 하는 코드이다. 하지만 보통 문제에서는 가중치가 같은 그래프 내에서 최단거리 알고리즘으로 사용된다. 따라서 최단거리 배열을 방문하면서 만들어줘야 하는데 이를 위한 코드는 다음과 같다.
BFS(G, u)
u.visited = 1
q.push(u)
while(q.size())
u = q.front()
q.pop()
for each v in G.adj[u]
if v.visited == false
v.visited = u.visited + 1
q.push(v)이때, 시작점이 다수일 경우에는 처음 큐에 push하는 지점이 다수가 되어야 하며, 해당 지점들을 모두 방문처리 한 상태에서 시작해야 한다.
DFS의 경우 메모리를 덜 사용하며, 절단점 들을 구할 수 있고, 코드가 좀 더 짧으며, 완전탐색의 경우 많이 사용한다. BFS의 경우 메모리를 더 많이 사용하며, 가중치가 같은 그래프에서 최단거리를 구할 수 있다.
문제에서 “퍼져나간다” 혹은 “탐색한다” 이러한 글자가 존재하는 경우 DFS, BFS를 생각해야 한다.
트리순회는 트리 구조에서 각각의 노드를 정확히 한 번만 체계적인 방법으로 방문하는 과정을 의미한다. 이는 노드를 방문하는 순서에 따라 후위순회, 전위순회, 중위순회, 레벨순회가 있다.
후위순회
이는 자식들의 노드를 방문하고 자신의 노드를 방문하는 것을 의미한다.
Postorder(node)
if node.visited == false
Postorder(node->left)
Postorder(node->right)
node.visited = true전위순회
이는 먼저 자신의 노드를 방문하고 그 다음 노드들을 방문하는 것을 의미한다.
Preorder(node)
if node.visited == false
node.visited = true
Preorder(node->left)
Preorder(node->right)중위순회
이는 왼쪽 노드를 먼저 방문 후 자신의 노드를 방문하고, 마지막으로 오른쪽 노드를 방문하는 것을 의미한다.
Inorder(node)
if node.visited == false
Inorder(node->left)
node.visited = true
Inorder(node->right)레벨순회
BFS와 동일하다.