그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조로 정점 (vertex)와 간선 (edge)들의 유한 집합이다
그래프는 수학적으로 G = (V, E)와 같이 표현하며 V(G)는 정점의 집합을, E(G)는 간선의 집합을 나타낸다
그래프의 종류
- 무방향 그래프
- V(G) = {A, B, C, D, E, F}
- E(G) = {(A, B), (A, D), (A, E), (B, C), (B, E), (E, F)}
- 방향 그래프
- V(G) = {A, B, C, D, E, F}
- E(G) = {<A, B>, <A, E>, <B, C>, <B, E>, <D, A>, <E, F>}
- <A, B>와 <B, A>는 서로 다른 간선
- 가중치 그래프 (네트워크)
차수 (Degree)와 경로
- 인접 정점 (adjacent vertex) : 간선에 의해 직접 연결된 정점
- 차수 : 해당 정점에 인접한 정점의 수
- 경로 : 정점 s로부터 정점 e까지의 모든 간선을 나열한 것
정점 A의 인접 정점 : B, C
정점 A의 차수 : 2
정점 A에서 정점 F까지의 경로 : {(A, B), (B, E), (E, F)}, {(A, E) , (E, F)}
그래프 표현 방법
- 인접 행렬 : 그래프를 정점의 수가 n이라면 n * n의 2차원 배열로 표현하는 방법
- 무방향 그래프는 대칭 / 방향 그래프는 비대칭 - 인접 리스트 : 그래프를 각각 정점에 인접한 정점들에 대해 연결 리스트로 표현하는 방법
그래프 탐색
깊이 우선 탐색 (DFS : Depth First Search)
한 루트를 따라가다가 막히면 마지막 갈림길로 되돌아가 다른 루트를 따라가는 순회 방법
DFS(v)
{
visit v;
for (u that unvisted v's adjacent vertex)
{
if (u is not visited)
{
DFS(u);
}
}
}재귀적 방법이나 스택을 사용하는 방법으로 구현 가능하다
너비 우선 탐색 (BFS : Breath First Search)
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점은 나중에 방문하는 순회 방법
BFS(v)
{
visit v;
insert v's unvisted adjacent vertex in queue;
if (queue is empty) return;
u = remove from queue;
BFS(u);
}
신장 트리 (Spanning Tree)
트리의 특수한 형태로 모든 정점들이 연결되어 있고 사이클을 포함하지 않는 트리
n개의 정점을 정확히 (n -1)개의 간선으로 연결
최소 신장 트리 (MST : Minimum Spanning Tree)
신장 트리 중 사용된 간선들의 가중치 합이 최소인 신장 트리
Kruskal's Algorithm
그리디 방법
간선 기반 알고리즘
생성된 여러 트리가 나중에 하나가 되는 방식
T = {}; // MST 간선 집합
A[n-1] = {sort E by weight}; // n : 정점의 수
while (number of T's edge < n - 1)
{
remove smallest edge in A;
if (edge does not make any cycle in (V, T + edge)
{
append edge in T;
}
}
=> (V, T) : MST
Prim's Algorithm
정점 기반 알고리즘
시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법
앞 단계에서 만드러진 신장 트리 집합에, 인접한 정점들 중 최저 간선으로 연결된 정점을 선택하여 트리를 확장
트리가 n -1개의 간선을 가질 때까지 계속됨
S = {a}; // 정점 집합, 시작 정점만 초기화
T = {}; // MST 간선 집합
while (number of T's edge < n - 1) // n : 정점의 수
{
C = {(x, y) | x ∈ V, y ∈ E - S};
remove smallest edge in C;
append y in S;
append edge in T;
}
=> (V, T) : MST
최단 경로 (SP : Shortest Path)
정점 i와 정점 j를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로
종류
- SPSP (Single Pair SP) : 한개의 출발점과 도착점
- SSSP (Single Source SP) : 한개의 출발점과 여러개의 도착점
- SDSP (Single Destination SP) : 여러개의 출발점과 한개의 도착점
- APSP (All Pairs SP) : 여러개의 출발점과 도착점
Dijkstra's Algorithm : SSSP
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
가중치는 음수가 아님
// v부터 모든 정점까지의 최단 거리
S = {v}
for 각 정점
D[w] = W[v][w]
while 모든 정점이 S에 포함될 때까지
u = S에 속하지 않는 정점 증 distance가 가장 적은 정점
S에 u 추가
for S에 없고 u에 인접 정점
D[z] = min(D[z], D[u] + W[u][z])
Floyd's Algorithm : APSP
모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
가중치가 음수여도 되나, 합이 음수 가중치를 갖는 사이클이 있어서는 안됨
\(d^k\)(i,j) : i에서 출발하여 k의 정점만을 경유하여 j로 가는 최단 경로의 거리
1. \(d^0\) = w // 초기치
2. for (k = 0 ~ n - 1) for (i = 0 ~ n - 1) for (j = 0 ~ n -1)
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
