비선형 자료구조 (그래프)
이번 포스트에서는 비선형 자료구조 중 하나인 그래프에 대하여 설명하겠습니다.
그래프
그래프는 간선으로 연결된 정점들의 모음을 표현한 자료구조입니다.
이때 정점과 정점을 연결하는 간선들이 방향을 가지지 않는 경우, 이 그래프를 무방향 그래프라고 합니다.
반대로, 방향을 가지는 경우 방향 그래프라고 정의합니다.
부분그래프는 그래프 G의 정점 V와 간선 E가 있을 때, 부분그래프 G'는 다음 수식을 만족합니다.
G' = (V', E'), V' 는 V에 속하고, E'는 E에 속해야합니다.
무방향 그래프 G 내 임의의 서로 다른 두 정점 u, v에 대해, u에서 v로 가는 경로가 존재한다면, G는 연결 되었다고 합니다.
이때, G 내에서 최대로 연결된 부분그래프를 연결요소 라고한다.
반대로 방향 그래프 G 에서 위 조건을 만족하면 각각 강력연결, 강력연결요소 라고합니다.
트리 또한 그래프 중 하나로 구별됩니다.
신장트리는 그래프 G의 모든 정점을 포함하면서 G 내 간선들로만 구성된 트리를 의미합니다.
이때, 최소비용 신장트리는 최소 비용을 갖는 신장 트리를 의미합니다.
여기서 비용은 가중치가 부여된 무방향 그래프 G의 신장 트리 T 내의 간선들의 가중치 합으로 정의됩니다.
최소비용 신장트리는 추후 포스트에서 서술할 크루스칼 알고리즘, 프림 알고리즘 등으로 찾을 수 있습니다.
그래프의 표현법
그래프는 인접 행렬 기반 방법과 인접 리스트 기반 방법으로 표현합니다.
인접행렬은 V^2의 공간을 요구하고, 인접리스트는 V+E의 공간을 요구합니다.
따라서, 그래프에서 표현할 양이 적다면, 인접리스트의 방법이 효율적이고, 그렇지 않다면 인접행렬이 효율적일 수 있습니다.
먼저 인접행렬은 정점 수가 n인 그래프를 n * n 크기의 2차원 배열 M에 표현하는 방법으로, 정점 i에서 정점 j로의 간선이 존재한다면, M[i][j]에 1을 저장하고, 그렇지않다면 0으로 저장하는 방법입니다.
|
1
2
3
4
5
6
|
#define N 4 //
int g[N][N];
void addEdge(int s, int e) {
g[s][e] = g[e][s] = 1; //무방향 그래프인 경우로 해석하기에 양쪽 정점으로 다 간선이 있다고 가정
}
|
cs |
다음은 인접리스트 방법입니다. 인접리스트는 정점 수 n인 그래프를 크기 n의 연결리스트 배열 L로 표현하는 방법으로, L[i]가 정점 i의 인접 정점들의 리스트를 참조하도록 표현합니다. 여기서 인접이란, 하나의 간선으로 연결된 두 정점들을 인접 하다고 정의합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
typedef struct Node {
int v;
struct Node *next;
} Node;
#define N 4
#define E 5
Node* head[N];
int e[E][2] = {{0,1}, {0,2}, {0,3}, {1,2}, {2,3}};
void addEdge(int s, int e) {
Node* x = (Node *)malloc(sizeof(Node));
x->v = e;
x->next = nullptr;
x->next = head[s];
head[s] = x;
}
|
cs |
그래프의 탐색
그래프의 탐색 방법으로는 깊이우선탐색(DFS), 너비우선탐색(BFS)가 있습니다.
먼저 깊이우선탐색입니다. 정점 v에서 시작할 때, DFS는 정점 v를 방문한 후, v의 각 미방문 인접 노드 w에 대해 DFS를 다시 적용하는 탐색방법입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
typedef struct Node {
int v;
struct Node* next;
}
void dfs(int v, int* visited) {
visited[v] = 1; //방문 표시
cout << v << "=>";
for(Node* p = head[v]; p != nullptr; p = p->next) { //현재 방문한 노드 v에 대해 인접한 노드를 모두 방문.
if(!visited[p->v]) dfs(p->v, visited); //미방문 노드 발견 시 dfs를 해당 미방문노드를 기준으로 재실행.
}
}
|
cs |
다음으로 너비우선탐색입니다. 정점 v에서 시작할 때, BFS는 정점 v를 방문한 후, 큐에 삽입하고, 공백 큐가 아닌 동안 큐에서 삭제하여 얻은 정점의 각 미방문 인접 노드를 방문 및 큐에 삽입하는 절차를 반복하는 탐색방법입니다.
|
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
|
typedef struct Node {
int v;
struct Node* next;
}
Node* qHead = nullptr;
Node* qTail = nullptr;
void bfs(int v) {
int visited[N] = {0};
visited[v] = 1;
cout << v << "=>";
addQueue(v) //일반적으로 코드를 구현해보실때는 c에서 큐 라이브러리를 불러와서 enqueue 연산을 수행하면 됩니다.
while(qHead != nullptr) { //이 부분또한 큐가 공백인지 확인하는 empty()를 사용하셔도 됩니다.
int v = removeQueue(); //이 부분도 동일합니다.
for(Node *p = gHead[v]; p != nullptr; p = p->next) {
if(!visited[p->v]) {
visited[p->v] = 1;
cout << v << "=>";
addQueue(p->v);
}
}
}
}
void addQueue(int v) { //enqueue
Node* x = (Node*)malloc(sizeof(Node));
x->v = v;
x->next = nullptr;
if(qHead == nullptr) qHead = qTail = x;
else {
qTail->next = x;
qTail = qTail->next;
}
}
int removeQueue() { //dequeue
if(qHead == nullptr) exit(-1);
Node* p =qHead;
qHead = qHead->next;
int v = p->v;
free(p);
if(qHead == nullptr) qTail = nullptr;
return v;
}
|
cs |
다음은 탐색 중 한 정점과 다른 한 정점으로의 최단경로를 찾는 탐색인 다익스트라 알고리즘입니다.
다익스트라 알고리즘은 최단경로가 결정되지 않은 노드 중 시작 노드 s로 부터 최단경로로 도달 가능한 노드 u를 찾고, 최단 경로 미결정 노드 중 u를 거쳐서 도달 할 수 있는 최단경로 미결정 노드들의 거리를 갱신하는 작업을 모든 노드의 최단경로를 찾을 때 까지 반복하는 탐색 알고리즘입니다.
|
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
|
int findMin() { //방문하지 않는 노드 중 최단거리 노드 찾아서 리턴
int minPos = -1;
double min = DBL_MAX;
for(int t = 0; t < N; t++) {
if(!found[t] && dist[t] < min) {
min = dist[t];
minPos = t;
}
}
return minPos;
}
void dijkstra(int s) {
for(int t = 0; t < N; t++) { //각 노드 초기화.
dist[t] = DBL_MAX;
found[t] = 0;
}
dist[s] = 0; //루트노드는 거리가 0
for(int i = 0; i < N; i++) {
int u = findMin(); //최단거리 노드를 찾음
found[u] = 1; //해당노드는 최단거리를 찾았다고 표현
for(int v = 0; v < N; v++) {
if(!found[v] && dist[u] + w[u][v] < dist[v]) { //아직 최단거리를 찾지 않는 노드 중 u 노드를 거쳐서 도달할 수 있는 노드들의 거리를 갱신함. (u가 최단거리니까 거쳐야함)
dist[v] = dist[u] + w[u][v];
}
}
}
}
|
cs |
이렇게 그래프에 대해서 포스트해보았습니다.
다음 포스트에서는 해시테이블에 대해서 포스트하도록 하겠습니다.