정점과 간선
정점(vertex)는 노드라고도 불리며 그래프를 형성하는 기본 단위이다.
정점은 분할할 수 없는 객체이자 '점'으로 표현되는 위치, 사람, 물건 등이 될 수 있다.
간선(Edge)은 정점을 잇는 선을 의미한다. 관계, 경로 등이 될 수 있다.
예를 들어
"어떠한 위치나 어떠한 사람"으로부터 "무언가를 통해 간다"라고 했을 때 "어떠한 위치나 어떠한 사람" 정점(Vertex)이 되고 "무언가를 통해 간다"는 간선(Edge)이 된다.
흔히 u와 v라는 변수를 많이 사용하는데, u는 from, v는 to를 보통 의미한다.
indegree outdegree
점점으로 나가는 간선을 해당 정점의 outdegree라고 하며 들어오는 간선을 해당정점의 indegree라고 한다.
트리
트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미한다.
- 부모, 자식 계층 구조를 가진다.
- V - 1 = E 라는 특징이 있다. 간선 수는 노드수 - 1이다.
- 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나밖에 없다.
루트노드
가장 위에 있는 노드. 보톤 트리를 탐색할 때 루트노드를 중심으로 탐색을 함.
내부노드
루프노드와 리프노드 사이에 있는 노드
리프노드
자식노드가 없는 노드
이진트리
각각의 노드의 자식노드 수가 2개 이하로 구성되어 있는 트리.
이진탐색트리(BST, Binary Search Tree)
이진트리의 일종으로 노드의 오른쪽 하위 트리에는 노드의 값보다 큰 값이 있는 노드만 포함되고 왼쪽 하위트리에는 노드의 값보다 작은 값이 들어있는 트리.
탐색, 삽입, 삭제, 수정 모두 O(logN) 이다.
그래프 구현과 탐색 1. 인접행렬
컴퓨터에게 내가 이러한 그래프를 그렸다고 알려줄 표현방법으로는 인접행렬과 인접리스트가 있다.
인접행렬이란 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다. 정사각형 행렬의 각 요소가 0또는 1이라는 값으로 가짐을 의미한다. 0은 두 정점 사이의 경로가 없음을 의미하며 1은 두 정점 사이의 경로가 있음을 의미한다.
bool a[4][4] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 0},
{1, 0, 0, 0},
};
예시) 3번 노드에서 5번 노드로 가는 단방향 경로가 있고, 이를 인접행렬로 표현?
-> a[3][5] = 1;
예시) 3번 노드에서 5번 노드로 가는 양방향 경로가 있고, 이를 인접행렬로 표현?
-> a[3][5] = 1; a[5][3] = 1;
그래프 구현과 탐색 2. 인접리스트
인접리스트(adjacency list)는 그래프에서 정점과 간선의 관계를 나타내는 연결리스트를 의미한다.
const int V = 4;
vector<int> adj[V];
adj[0].push_back(1);
adj[0].push_back(2);이런 식으로 구현.
4방향탐색과 방향벡터
어떠한 y, x가 주어졌을 때 y, x를 중심으로 상하좌우 4가지 방향으로 탐색은 어떻게 하나?
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
for(int i = 0 ; i < 4; i++){
ny = y + dy[i];
nx = x + dx[i];
}깊이 우선 탐색(DFS, Depth First Search)
DFS는 그래프를 탐색할 때 쓰는 알고리즘이며 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방분하여 방문한 정점은 다시 방문하지 안흐며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘
Pseudocode
DFS(u, adj)
u.visited = true;
for each v ∈ adj[u]
if v.visited == false
DFS(v, adj)dfs를 구현하는 방법은 크게 두 가지가 있다.
방법 1: 돌다리를 두들겨보다.
void dfs(int here){
visited[here] = 1;
for(int there : adj[here]){
if(visited[there]) continue;
dfs(there);
}
}다만 이럴 경우 시작지점에 대한 방문처리를 해주어야 한다.
예를 들어 1, 2, 3, 4지점을 탐색한다고 하고 1지점부터 탐색을 이어나간다고 하면
visited[1] = 1;
dfs(1);과 같이 해야한다.
방법 2: 못 먹어도 Go
void dfs(int here){
if(visited[here]) return;
visited[here] = 1;
for(int there : adj[here]{
dfs(there);
}
}너비 우선 탐색(BFS, Breadth First Search)
BFS는 그래프를 탐색하는 알고리즘이며 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기 전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘이다.
같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰인다.
Pseudocode1
먼저 시작지점인 u를 "방문처리"를 하고 큐에 푸시한다. 그리고 q.size() 만큼 while 반복문을 돌면서 큐 앞단에 있는 u를 다시 끄집어내서 그 u를 중심으로 인점한 노드들을 탐색한다. 방문한 정점은 다시 방문하지 않고 방문처리를 하면서 큐에 푸시를 하며 방문처리를 한다.
BTS(G, u)
u.visited = 1;
q.push(u);
while(q.size()){
u = q.front();
q.pop();
for each v ∈ G.Adj[u]
if v.visited == false
v.visited = true (v.visited = u.visited + 1)
q.push(v)
}