그래프(Graph)
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조.
그래프는 간선 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분됨.
간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 또는 network라고 한다.
네트워크는 도시와 도시를 연결하는 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등을 추가로 표현할 수 있으므로 응용 분야가 매우 광범위하다.
인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
차수(degree) : 하나의 정점에 인접한 정점의 수 (undirected graph는 간선X2)
directed graph에서 (=<A,B>)
진입 차수(in-degree) : 외부에서 오는 간선의 수
진출 차수(out-degree) : 외부로 향하는 간선의 수
undirected graph에서(=(A,B))
모든 정점쌍에 대해 항상 경로가 존재한다면 그래프G는 연결되어있다고 한다. 연결 그래프(connected graph)라 부른다. 그렇지 않은 그래프는 비연결 그래프라고 함.
- 완전 그래프(complete graph) : 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
- undirected complete graph의 정점 수가 n인 경우 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는
n*(n-1)/2
트리는 그래프릐 특수한 형태로, 사이클을 가지지 않는 연결 그래프임.
경로 길이(path length) : 경로를 구성하는 데 사용된 간선의 수
단순 경로(simple path) : 경로 주 반복되는 간선이 없을 경우
사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
그래프 표현 방법
1. 2차원 배열을 이용한 인접 행렬(adjacency matrix)
2. 연결리스트를 이용한 인접 리스트(adjacency list)
그래프 문제 특성에 따라 각각 메모리 사용량과 처리 시간 등에서 장단점 가짐.
1. adjacency matrix 인접 행렬
n개의 정점을 갖는 그래프를 표현하기 위해 간선 수와 부관하게 항상 n²의 메모리 공간이 필요함.
그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 겨우 적합하지만, 간선이 얼마 없는 희소 그래프(sparse graph)의 경우 메모리 낭비가 커, 적합하지 않음.
- 간선의 존재 여부를 O(1) 시간 안에 즉시 알 수 있음. => M[i][j] 값을 조사하면 됨.
- 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(n) => 정점 i에 대한 차수 : i번째 행의 값 모두 더함.
- 모든 간선의 수를 구하기 위해 인접 행렬 전체를 조사해야 하므로 O(n²) 시간 요구됨.
2. adjacency list 인접 리스트
그래프의 각 정점에 인접한 정점들을 연결리스트로 표시한 것. 연결 리스트의 node들은 인접 정점을 저장하게 됨.
각 연결리스트들은 head pointer를 가지고 있고, 이들은 배열로 구성되어있다. 따라서 정점의 번호만 알면 번호를 배열의 index로 하여 각 정점의 연결리스트에 쉽게 접근할 수 있음.
인접 리스트의 각 연결리스트에 정점들이 입력되는 순서에 따라 연결리스트 내에서 정점의 순서가 달라질 수 있음.
따라서 정점의 수가 n개, 간선 수가 e개인 무방향 그래프를 표시하기 위해서는 n개의 연결리스트가 필요하고, n개의 head포인터와 2e개의 노드가 필요하므로 간선의 개수가 적은 희소그래프(sparse graph) 표현에 적합.
전체 간선의 수를 알아내려면 헤더 노드를 포함해 모든 인접 리스트를 조사해야하므로 O(n+e)연산 소요
* 깊이 우선 탐색(Depth First Search)
미로 탐색에서 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 다시 돌아와서 다른 방향으로 다시 탐색 진행하는 방법과 유사.
DFS탐색은 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
DFS구현 방법은 2가지 방법이 있는데,
1.순환 호출(재귀)
2.Stack을 사용해 방문한 정점들을 스택에 저장했다가 다시 꺼내 작업하는 것.
*DFS는 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프가 인접리스트로 표현되어있다면 O(n+e), 인접 행렬로 표현되어있다면 O(n²)이다.
=>spares graph인 경우 인접 리스트의 사용이 더 효울적.
* 너비 우선 탐색(Breadth First Search)
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.
BFS구현 방법
1. Queue
초기 상태의 큐는 시작 정점만 저장되고, BFS 탐색 과정은 queue가 empty상태가 될 때까지 계속 함.
BFS의 특징은 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색이 진행된다는 것임.
여기서 거리란, 시작 정점으로부터 어떤 정점까지의 경로 중 가장 짧은 경로의 길이를 뜻함. 거리가 d인 정점들을 모두 방문한 후 (d+1)인 정점들을 모두 방문하는 순서로 탐색한다.
*인접리스트로 표현되어있다면 O(n+e), 인접 행렬로 표현되어있다면 O(n²)이다.
DFS와 같이 spares graph인 경우 인접 리스트를 사용하는 것이 더 효율적.
DFS, BFS 구현 문제
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define NMAX 1001
#define MMAX 10001
using namespace std;
int N, M, V;
int visit[NMAX];
vector<int> G[NMAX];
vector<int> ans[2];
void dfs(int v) {
visit[v] = 1;
cout << v << " ";
int vsize = G[v].size();
for (int i = 0; i < vsize; i++) {
int nxt = G[v][i];
if (visit[nxt]) continue;
dfs(nxt);
}
}
void init_visit() {
for (int i = 1; i <= N; i++) {
visit[i] = 0;
}
}
void bfs() {
queue<int> q;
q.push(V);
visit[V] = 1;
while (!q.empty()) {
int cur = q.front();
cout << cur << " ";
q.pop();
int vsize = G[cur].size();
for (int i = 0; i < vsize; i++) {
int nxt = G[cur][i];
if (visit[nxt]) continue;
q.push(nxt);
visit[nxt] = 1;
}
}
}
int main(void) {
cout.tie(NULL);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> N >> M >> V;
for (int i = 0; i < M ; i++) {
int u, v;
cin >> u >> v;
//양방향 연결
G[u].push_back(v);
G[v].push_back(u);
}
//정점 번호가 작은 것부터 방문
for (int i = 0; i < N; i++) {
sort(G[i].begin(), G[i].end());
}
dfs(V);
init_visit();
cout << "\n";
bfs();
return 0;
}
|
cs |
신장 트리(spanning tree)
그래프 내의 모든 정점을 포함하는 트리. 트리의 특수한 형태.
1. 모든 정점들이 연결되어 있어야 함
2. 사이클을 포함해서는 안됨.
3. 따라서 n개의 정점이 정확히 (n-1)개의 edge로 연결됨
spanning tree는 통신 네트워크 구축에 사용된다.
n개의 위치를 연결하는 통신 네트워크를 최소 링크를 이용해 구축하고자 할 때 최소 링크 수는 n-1이 되고, 따라서 신장 트리들이 가능한 대안이 되는데
각 링크의 구축 비용이 다르다. 따라서 edge에 가중치를 붙인 링크의 구축 비용까지 고려해서 최소 비용의 신장트리를 선택해야 한다.
Minimum Spanning Tree(MST, 최소 비용 신장 트리)
spanning tree 중 사용된 edge wieght 합이 최소인 tree.
MST 응용 예
1) 도로 건설 - 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록
2) 전기 회로 - 단자들을 모두 연결하면서 전선 길이가 가장 최소가 되도록
3) 통신 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성
4) 배관 - 파이프를 모두 연결하면서 총 길이가 최소가 되도록
MST를 구하는 방법 중 대표적으로 Kruskal, Prim이 제안한 알고리즘이 대표적이며
이 알고리즘들은 MST edge weight 합이 최소여야하고, 반드시 (n-1)개의 간선만 사용해야하며, 사이클이 포함되어서는 안된다는 조건들을 적절히 이용하고 있다.
Kruskal의 MST 알고리즘
참고 : https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html
greedy mathod(탐욕적인 방법)을 이용한다.
결정할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하여 최종적 해답에 도달한다.
그 순간의 선택이 그 당시에는 최적이다. 그러나 최적이라 생각했던 해답을을 모아 최종적 답을 만들었다 해서 그 해답이 전체적 관점에서 최적이라는 보장은 없다.
따라서 greedy mathod는 항상 최적의 해답을 주는지 반드시 검증해야 이 알고리즘은 최적의 해답을 주는 것으로 증명되어있다.
Kruscal 동작
1. e개의 간선을 가중치들의 오름차순으로 정렬
2. 정렬된 edge list에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
3. 현재 MST 집합에 추가한다.
다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클이 생성되는지 체크해야 한다.
새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결할 때 사이클이 형성되는데,
즉 양끝 정점이 같은 집합에 속하면 간선을 추가했을 경우 사이클이 형성된다. 그러나 서로 다른 집학ㅂ에 속하는 경우 두 정점을 연결해도 사이클이 형성되지 않는다. 따라서 지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지 먼저 검사해야하는데, 이 검사를 위한 알고리즘을 union-find 알고리즘이라 한다.
Kruskal 알고리즘에 의해서만 사용되는 건X 일반적으로 널리 사용됨.
union-find 알고리즘을 이용하면 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다.
따라서 간선 e개를 퀵 정렬과같은 효율적인 알고리즘으로 정렬한다면 O(elog₂e)가 된다.
Prim의 MST 알고리즘
시작 정점에서부터 출발해 신장 트리 집합을 단계적으로 확장해 나가는 방법.
시작 단계에서는 시작 정점만 신장트리 집합에 포함됨.
Prim 알고리즘은 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중 최소 간선으로 연결된 정점을 선택해 트리를 확장하는데, 이 과정을 n-1개의 edge를 가질 때까지 반복한다.
Kruscal 알고리즘은 edge 선택을 기반으로 하고, 이전 단계에서 만들어진 신장트리와는 상관없이 무조건 최소 간선만을 선택하는 방법인데 비해 , Prim 알고리즘은 정점 선택을 기반으로 하며, 이전 단계에서 만들어진 신장트리를 확장하는 방식이다.
결과는 Kruskal 알고리즘과 같다.
주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하여 O(n²) 복잡도 가짐.
희소 그래프를 대상으로 할 경우에는 Kruskal, 밀집한 그래프의 경우에는 Prim이 효율적.
최단 경로(shortest path)
: 정점 u, 정점가중치의 합이 최소가 되는 문제.
최단 경로를 발견하는 알고리즘 2가지
1. Dijksta 알고리즘
: 하나의 시작 정점에서 모든 다른 정점까지의 최단 경로 찾음
최단 경로는 경로의 길이 순으로 구해짐
2. Floyd 알고리즘
: 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾음
topological sort(위상 정렬)
방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프의 위상정렬이라고 함.
방향 그래프를 대상으로 하는 알고리즘
1. 진입 차수가 0인 정점 선택
2. 선택된 정점과 여기 부속된 모든 간선 제거
3. 이처럼 진입 차수가 0인 정점의 선택과 삭제 과정을 반복해 모든 정점이 선택/삭제되면 알고리즘 종료
진입 차수 0인 정점이 여러 개 존재할 경우 어떤 정점을 선택해도 무방해, 복수의 위상 순서가 있을 수 있다.
선택되는 정점의 순서를 topological order(위상 순서)라고 하며
남아 있는 정점 중 진입 차수 0이 없다면 이런 그래프로 표현된 프로젝트는 실행 불가능한 프로젝트가 되고 알고리즘이 중단된다.