알고리즘 & 자료구조 - 그래프, DFS&BFS
개념
그래프는 1개 이상의 정점 (vertex / node)들과 0개 이상의 간선 (edge)들로 이루어진 자료구조입니다.
- 정점: A, B, C
- 간선: 2개 (A와 B를 잇는 간선, A와 A를 잇는 간선)
그래프의 종류
- Undirected Graph (무방향 그래프): 방향이 없는 간선들로 이루어진 그래프
(1)
- Directed Graph (방향 그래프): 간선에 방향이 존재하는 그래프
(2)
- Weighted Graph (가중 그래프): 간선에 가중치가 존재하는 그래프 (Undirected Graph도 Weighted Graph가 될 수 있음)
(3)
- 그 외에 simple graph, multigraphs, pseudo graph 등이 존재합니다.
정점의 degree
- degree of vertex: 정점에 연결된 간선의 개수
- in-degree (deg-): 해당 정점이 도착지인 간선의 개수
- out-degree (deg+): 해당 정점이 출발지인 간선의 개수
ex) 그림(1)에서 degree of A = 3, degree of B = 1
ex) 그림(2)에서 deg-(A) = 1, deg+(A) = 2, deg-(B) = 1, deg+(B) = 0
표현
1. 인접행렬
그래프가 n개의 정점을 가질 때 n*n의 2차원 배열을 생성해 정보를 저장합니다.
int adjMatrix[10][10]; //인접행렬 선언
adjMatrix[i][j] = 1 //i정점에서 j정점으로 가는 간선이 존재
adjMatrix[i][j] = 0 //그런 간선이 존재하지 않음
예시
위 그래프에 대한 인접행렬은 다음과 같이 표현할 수 있습니다.
| \ | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 0 | 1 |
| 2 | 0 | 0 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 | 1 |
| 4 | 0 | 0 | 1 | 0 | 0 |
| 5 | 1 | 1 | 1 | 0 | 0 |
방향 그래프도 같은 방식으로 표현할 수 있습니다.
가중 그래프의 경우 간선이 존재하면 그 간선의 가중치를 1 대신 적어서 표현할 수 있습니다.
2. 인접리스트
인접행렬로 표현하면 특정 정점 사이에 간선이 존재하는지 바로 알 수 있다는 장점이 있지만, 아무래도 메모리를 많이 사용한다는 단점이 있습니다.
인접리스트는 해당 정점에서 이웃한 정점들을 저장하고, 이를 표현하기 위해 vector를 사용할 수 있습니다.
vector<int> adjList[5]; //인접리스트 선언
//adjMatrix[1][3] = 1이면
adjList[1].push_back(3); //과 같이 처리!
위 표를 인접리스트로 나타내면 다음과 같습니다.
| adjList[i] | |||
|---|---|---|---|
| adjList[1] | 3 | 5 | |
| adjList[2] | 5 | ||
| adjList[2] | 1 | 4 | 5 |
| adjList[2] | 3 | ||
| adjList[2] | 1 | 2 | 3 |
adjMatrix에서 값이 0이던 부분을 생략하므로 메모리와 순회 시간을 아낄 수 있습니다.
가중 그래프에서는
vector<int> adjList[5];
대신
vector<pair<int, int>> adjList[5];
와 같이 선언하고 pair의 first를 연결된 정점의 번호로, second를 간선의 가중치로 표현할 수 있습니다.
탐색
그래프 자료구조를 통해 저장했다면 탐색하는 방법도 필요할 것입니다. 그래프를 탐색하는 방법에는 크게 DFS와 BFS가 있습니다.
1. DFS
DFS는 DepthFirstSearch (깊이 우선 탐색)의 약자입니다. DFS의 탐색 순서를 그림을 통해 보면
즉 진행하면서 더이상 갈 곳이 없을 때까지 탐색한 뒤, 다시 뒤로 돌아오는 방식이기 때문에 스택, 재귀를 이용해 구현할 수 있습니다.
스택을 이용할 때 작동 방식에 대해 알아보겠습니다.
주의할 점은 stack에 정점 번호를 push할 때가 아닌 pop할 때 그 정점을 탐색합니다.
시작 노드를 스택에 push합니다.
| Stack |
|---|
| 1 |
stack에서 pop을 하고(1) 그곳에서 연결된 정점들(2, 4, 5)을 stack에 push합니다.
이때 2, 4, 5 순서대로 push하지 않고 5, 4, 2 순서대로 push하는 이유는 그림의 순서대로 탐색하게 하기 위해서 입니다. (2, 4, 5 순서대로 push해도 dfs를 하는데는 문제 없습니다.)
| Stack |
|---|
| 2 |
| 4 |
| 5 |
stack에서 pop을 하고(2) 그곳에서 연결된 정점(3)을 stack에 push합니다.
| Stack |
|---|
| 3 |
| 4 |
| 5 |
stack에서 pop을 합니다. (3)
다만 이때 3번 정점에서 더 갈 수 있는 정점이 없기 때문에 push하지 않습니다.
| Stack |
|---|
| 4 |
| 5 |
stack에서 pop을 합니다. (4)
다만 이때 4번 정점에서 더 갈 수 있는 정점이 없기 때문에 push하지 않습니다.
| Stack |
|---|
| 5 |
stack에서 pop을 하고(5) 그곳에서 연결된 정점(6)을 stack에 push합니다.
| Stack |
|---|
| 6 |
stack에서 pop을 하고(6) 그곳에서 연결된 정점(7)을 stack에 push합니다.
| Stack |
|---|
| 7 |
stack에서 pop을 합니다. stack을 다 비웠기 때문에 탐색을 종료합니다.
DFS 코드
DFS_STACK_CODE
#include <iostream>
#include <stack>
#define MAX_NODE 50
using namespace std;
int N;
bool visited[MAX_NODE+1] = { false,};
int adjMatrix[MAX_NODE+1][MAX_NODE+1] = { 0,};
~~~
//N 입력받기
//adjMatrix 설정
~~~
void DFS(int start) {
stack<int> s;
s.push(start);
visited[start] = true;
while (!s.empty()) {
int cur = s.top();
s.pop();
cout << cur << " ";
for (int i = N; i >= 1; i--) { //다음 방문할 정점 살펴보기
if (adjMatrix[cur][i] == 1 && visited[i] == false) {
visited[i] = true;
s.push(i);
}
}
}
}
또는 재귀로 구현할 수도 있습니다.
DFS_RECURSION_CODE
#include <iostream>
#define MAX_NODE 50
using namespace std;
int N;
bool visited[MAX_NODE+1] = { false,};
int adjMatrix[MAX_NODE+1][MAX_NODE+1] = { 0,};
~~~
//N 입력받기
//adjMatrix 설정
~~~
void DFS(int start) {
cout << start << ' ';
visited[start] = true;
for (int i = 1; i <= N; i++) { //i=다음 방문할 정점
if (visited[i]) continue; //이미 방문했거나
if (!adjMatrix[start][i]) continue; //연결되어있지 않으면 건너뛰기
DFS(i);
}
}
2. BFS
BFS는 BreadthFirstSearch의 (너비 우선 탐색)의 약자입니다. BFS의 탐색 순서를 그림을 통해 보면
DFS와 다른 점은 DFS에서는 한 정점에서 계속 탐색을 진행했지만 BFS에서는 한 정점에서 주변 이웃한 노드들까지만 탐색을 한 뒤 탐색 순번을 넘겨준다는 것입니다.
이는 큐 자료구조를 이용해 구현할 수 있습니다.
큐를 이용할 때 작동 방식에 대해 알아보겠습니다.
이번에도 마찬가지로 queue에서 pop할 때 그 정점을 탐색합니다.
시작 노드를 큐에 push합니다.
| Queue | |
|---|---|
| front | 1 |
queue에서 pop을 하고(1) 그곳에서 연결된 정점들(2, 4, 5)를 queue에 push합니다.
이때 같이 push된 2, 4, 5는 탐색에서 같은 우선순위를 지닌다 생각하시면 됩니다.
| Queue | |||
|---|---|---|---|
| front | 2 | 4 | 5 |
queue에서 pop을 해 2번 정점을 탐색하고 그곳에서 연결된 정점(3)을 queue에 push합니다.
이때 queue를 이용해 back에 push되기 때문에 미리 저장된 4, 5번보다 탐색 순위가 늦게 되고, 이런 원리로 너비 우선 탐색을 진행할 수 있습니다.
| Queue | |||
|---|---|---|---|
| front | 4 | 5 | 3 |
queue에서 pop을 해 4번 정점을 탐색하고 더이상 방문 가능한 이웃한 정점이 없으므로 넘어갑니다.
| Queue | ||
|---|---|---|
| front | 5 | 3 |
queue에서 pop을 해 5번 정점을 탐색하고 연결된 정점(6)을 push합니다.
| Queue | ||
|---|---|---|
| front | 3 | 6 |
queue에서 pop을 해 3번 정점을 탐색하고 더이상 방문 가능한 이웃한 정점이 없으므로 넘어갑니다.
| Queue | |
|---|---|
| front | 6 |
queue에서 pop을 해 6번 정점을 탐색하고 연결된 정점(7)을 push합니다.
| Queue | |
|---|---|
| front | 7 |
queue에서 pop을 해 7번 정점을 탐색하고 큐가 비었으므로 BFS를 종료합니다.
BFS 코드
BFS_CODE
#include <iostream>
#include <queue>
#define MAX_NODE 50
using namespace std;
int N;
bool visited[MAX_NODE+1] = { false,};
int adjMatrix[MAX_NODE+1][MAX_NODE+1] = { 0,};
~~~
//N 입력받기
//adjMatrix 설정
~~~
void BFS(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
cout << cur << " ";
for (int i = 1; i <= N; i++) {
if (adjMatrix[cur][i] == 1 && visited[i] == false) {
visited[i] = true;
q.push(i);
}
}
}
}
감사합니다.