[알고리즘] DFS, BFS
탐색 알고리즘 DFS/BFS
DFS(Depth First Search), BFS(Breadth Fisrt Search)는 모두 탐색 알고리즘으로,
그래프를 탐색하는 과정에서 깊이를 우선으로 하는 지 (DFS),
너비를 우선으로 하는 지 (BFS)로 각 알고리즘의 특징을 나눌 수 있다.
1. DFS(Depth First Search) - 깊이 우선 탐색
DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 다음 그래프를 보고 DFS를 이해하여 보겠다.
위 그래프에서 시작 노드를 A로 하였을 때의 DFS 탐색 순서를 구해보고자 한다.
이때 스택을 활용하여 DFS 탐색 순서를 확인해 볼 수 있다.
* 노드를 스택에 넣는 행위를 방문한 것으로 정의 *
1. 시작 노드 A를 탐색한다(A를 방문한 것으로 정의), A의 인접 노드 B, C, D를 순서대로 스택에 push한다. // 탐색: A , 스택: B, C, D
2. 스택에서 pop을 진행하고 pop된 D를 탐색한다, D의 인접 노드 중 방문한 적이 없는 H를 스택에 push한다. // 탐색: A->D , 스택: B, C, H
3. pop 진행 H 탐색, H의 인접 노드 중 방문한 적이 없는 F, I를 push한다. // 탐색: A->D->H , 스택: B, C, F, I
4. pop 진행 I 탐색, I의 인접 노드 중 방문한 적이 없는 G를 push한다. // 탐색: A->D->H->I , 스택: B, C, F, G
5. pop 진행 G 탐색, G의 인접 노드 중 방문한 적이 없는 E를 push한다. // 탐색: A->D->H->I->G , 스택: B, C, F, E
6. pop 진행 E 탐색, E의 인접 노드 중 방문한 적이 없는 노드가 없음으로 push하지 않고 끝낸다. // 탐색: A->D->H->I->G->E , 스택: B, C, F
7. pop 진행 F 탐색, F의 인접 노드 중 방문한 적이 없는 노드가 없음으로 push하지 않고 끝낸다. // 탐색: A->D->H->I->G->E->F , 스택: B, C
8. pop 진행 C 탐색, C의 인접 노드 중 방문한 적이 없는 노드가 없음으로 push하지 않고 끝낸다. // 탐색: A->D->H->I->G->E->F->C , 스택: B
9. pop 진행 B 탐색, B의 인접 노드 중 방문한 적이 없는 노드가 없음으로 push하지 않고 끝낸다. // 탐색: A->D->H->I->G->E->F->C->B , 스택:
10. 스택이 비었기에 탐색을 종료한다.
” A->D->H->I->G->E->F->C->B “ 순서로 연결된 모든 노드들을 DFS 알고리즘에 맞추어 탐색하였다.
DFS를 실행할 때, 스택에 담기는 인접 노드의 순서에 따라 DFS의 탐색 결과는 다양한 경우가 나올 수 있음을 인지한다.
C++ 객체를 사용해 인접행렬을 기반으로 한 그래프에서 (위 그림 그래프 사용) DFS 메소드를 구현하면 아래와 같다.
이때 아래 코드는 스택이 아닌 재귀호출을 이용하여 DFS를 구현하였다.
#define MAX_VTXS 9
class AdjMatGraph{ // 인접 행렬 그래프
protected:
int size;
char vertices[MAX_VTXS];
int adj[MAX_VTXS][MAX_VTXS];
public:
AdjMatGraph(){reset();}
void reset(){
size = 0;
for (int i = 0; i < MAX_VTXS; i++){
for (int j = 0; j < MAX_VTXS; j++){
setEdge(i, j, 0);
}
}
}
void setEdge(int i, int j, int val){ adj[i][j] = val; }
int getEdge(int i, int j){ return adj[i][j]; }
char getVertex(int i){ return vertices[i]; }
bool isEmpty(){ return size == 0; }
bool isFull(){ return size >= MAX_VTXS; }
void insertVertex(char name){
if(!isFull()) vertices[size++] = name;
else cout << "error, isFull" << endl;
}
void insertEdge(int u, int v){
setEdge(u, v, 1);
setEdge(v, u, 1);
}
};
class SrchAMGraph : public AdjMatGraph{ // 인접 행렬 그래프 상속, visited 추가
private:
bool visited[MAX_VTXS];
public:
void resetVisited(){ for (int i = 0; i < size; i++){ visited[i] = false; } }
bool isLinked(int u, int v){ return getEdge(u, v) != 0; }
void DFS(int v){ // DFS 구현 부분
visited[v] = true;
cout << getVertex(v) << " ";
for (int w = 0; w < size; w++){
if (isLinked(v, w) && visited[w] == false){
DFS(w); // 재귀 호출
}
}
}
};
main
SrchAMGraph g;
// 노드 추가
g.insertVertex('A'); // 0
g.insertVertex('B'); // 1
g.insertVertex('C'); // 2
g.insertVertex('D'); // 3
g.insertVertex('E'); // 4
g.insertVertex('F'); // 5
g.insertVertex('G'); // 6
g.insertVertex('H'); // 7
g.insertVertex('I'); // 8
g.insertVertex('J'); // error, isFull
// 간선 연결
g.insertEdge(0, 1);
g.insertEdge(0, 2);
g.insertEdge(0, 3);
g.insertEdge(1, 4);
g.insertEdge(2, 5);
g.insertEdge(3, 7);
g.insertEdge(4, 5);
g.insertEdge(4, 6);
g.insertEdge(5, 7);
g.insertEdge(6, 8);
g.insertEdge(7, 8);
g.resetVisited();
g.DFS(0);
cout << endl;
return 0;
output
error, isFull
A B E F C H D I G
왜 탐색 순서가 위에서와 다르나
- 앞서 말했 듯이 DFS의 탐색 순서는 스택에 노드를 넣는 순서에 따라 다양하게 나올 수 있다.
- DFS의 절대 목표는 결국 탐색이기에 연결된 모든 노드를 순회하는 것이 제대로 구현되었는 지가 중요하다.
- 코드로 구현한 DFS 탐색 순서도 깊이를 우선으로 탐색하기에 DFS 결과 중 하나가 제대로 출력되었다고 볼 수 있다.
1. BFS(Breadth First Search) - 너비 우선 탐색
BFS는 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다. DFS에서와 같은 그래프로 BFS를 이해하여 보겠다.
시작 노드를 A로 하였을 때의 BFS 탐색 순서를 구해보고자 한다.
이때 큐를 활용하여 BFS 탐색 순서를 확인해 볼 수 있다.
* 노드를 큐에 넣는 행위를 방문한 것으로 정의 *
1. 시작 노드 A를 탐색한다(A를 방문한 것으로 정의), A의 인접 노드 B, C, D를 순서대로 큐에 enqueue한다. // 탐색: A , 큐: B, C, D
2. 큐에서 dequeue를 진행하고 dequeue된 B를 탐색한다, B의 인접 노드 중 방문한 적이 없는 E를 큐에 enqueue한다. // 탐색: A->B , 큐: C, D, E
3. dequeue 진행 C 탐색, C의 인접 노드 중 방문한 적이 없는 F를 enqueue한다. // 탐색: A->B->C , 큐: D, E, F
4. dequeue 진행 D 탐색, D의 인접 노드 중 방문한 적이 없는 H를 enqueue한다. // 탐색: A->B->C->D , 큐: E, F, H
5. dequeue 진행 E 탐색, E의 인접 노드 중 방문한 적이 없는 G를 enqueue한다. // 탐색: A->B->C->D->E , 큐: F, H, G
6. dequeue 진행 F 탐색, F의 인접 노드 중 방문한 적이 없는 노드가 없음으로 enqueue하지 않고 끝낸다. // 탐색: A->B->C->D->E->F , 큐: H, G
7. dequeue 진행 H 탐색, H의 인접 노드 중 방문한 적이 없는 I를 enqueue한다. // 탐색: A->B->C->D->E->F->H , 큐: G, I
8. dequeue 진행 G 탐색, G의 인접 노드 중 방문한 적이 없는 노드가 없음으로 enqueue하지 않고 끝낸다. // 탐색: A->B->C->D->E->F->H->G , 큐: I
9. dequeue 진행 I 탐색, I의 인접 노드 중 방문한 적이 없는 노드가 없음으로 enqueue하지 않고 끝낸다. // 탐색: A->B->C->D->E->F->H->G->I , 큐:
10. 큐가 비었기에 탐색을 종료한다.
” A->B->C->D->E->F->H->G->I “ 순서로 연결된 모든 노드들을 BFS 알고리즘에 맞추어 탐색하였다.
BFS 역시 DFS와 마찬가지로 큐에 담기는 인접 노드의 순서에 따라 다양한 탐색 결과가 나올 수 있다.
C++ 객체를 사용해 인접 리스트를 기반으로 한 그래프에서 (위 그림 그래프 사용) BFS 메소드를 구현하면 아래와 같다.
#define MAX_VTXS 9
#define PUSH 1
#define POP 2
class Queue {
private:
int front;
int rear;
int lastOp;
int data[MAX_VTXS];
public:
Queue() {
front = 0;
rear = 0;
lastOp = 0;
}
~Queue() {}
int isEmpty() {
if (front == rear && lastOp != PUSH) {
return 1;
} else return 0;
}
bool isFull() {
if (front == rear && lastOp == PUSH) return 1;
else return 0;
}
void enqueue(int i) {
if (!isFull()) {
rear = (rear + 1) % MAX_VTXS;
this->data[rear] = i;
lastOp = PUSH;
}
}
int dequeue() {
if (!isEmpty()) {
lastOp = POP;
front = (front + 1) % MAX_VTXS;
return data[front];
}
return 0;
}
void printQ() {
int numberOfQ;
numberOfQ = rear > front ? rear - front : (rear + MAX_VTXS) - front;
int index = front + 1;
for (int i = 0; i < numberOfQ; i++) {
cout << data[(index + i) % MAX_VTXS] << " ";
}
cout << endl;
}
};
class Node {
protected:
int id;
Node* link;
public:
Node(int i, Node* l = nullptr) {
id = i;
link = l;
}
~Node() { if (link != nullptr) delete link; }
int getId() { return id; }
Node* getLink() { return link; }
void setLink(Node* l) { link = l; }
};
class AdjListGraph {
protected:
int size;
char vertices[MAX_VTXS];
Node* adj[MAX_VTXS];
bool visited[MAX_VTXS];
public:
AdjListGraph() { size = 0; }
~AdjListGraph() { reset(); }
void reset() {
for (int i = 0; i < size; i++) {
if (adj[i] != nullptr) delete adj[i];
}
}
void insertVertex(char val) {
if (!isFull()) {
vertices[size] = val;
adj[size++] = nullptr;
} else cout << "error, isFull" << endl;
}
char getVertex(int v) { return vertices[v]; }
void insertEdge(int u, int v) {
adj[u] = new Node(v, adj[u]);
adj[v] = new Node(u, adj[v]);
}
Node* adjacent(int v) { return adj[v]; }
bool isFull() { return size >= MAX_VTXS; }
bool isEmpty() { return size == 0; }
bool isLinked(int u, int v) {
Node* temp = adj[u];
while (temp != nullptr) {
if (temp->getId() == v) {
return true;
}
temp = temp->getLink();
}
return false;
}
void BFS(int v) {
resetVisited();
visited[v] = true;
cout << getVertex(v) << " ";
Queue q;
q.enqueue(v);
while (!q.isEmpty()) {
int u = q.dequeue();
Node* temp = adj[u];
while (temp != nullptr) {
int w = temp->getId();
if (!visited[w]) {
visited[w] = true;
cout << getVertex(w) << " ";
q.enqueue(w);
}
temp = temp->getLink();
}
}
}
void resetVisited() {
for (int i = 0; i < size; i++) {
visited[i] = false;
}
}
};
main
AdjListGraph g;
g.insertVertex('A');
g.insertVertex('B');
g.insertVertex('C');
g.insertVertex('D');
g.insertVertex('E');
g.insertVertex('F');
g.insertVertex('G');
g.insertVertex('H');
g.insertVertex('I');
g.insertEdge(0, 1); // A-B
g.insertEdge(0, 2); // A-C
g.insertEdge(0, 3); // A-D
g.insertEdge(1, 4); // B-E
g.insertEdge(2, 5); // C-F
g.insertEdge(3, 7); // D-H
g.insertEdge(4, 5); // E-F
g.insertEdge(4, 6); // E-G
g.insertEdge(5, 7); // F-H
g.insertEdge(6, 8); // G-I
g.insertEdge(7, 8); // H-I
cout << "BFS: ";
g.resetVisited();
g.BFS(0);
cout << endl;
return 0;
output
BFS: A D C B H F E I G
DFS에서와 같은 이유로 다른 탐색 순서
- 큐에 담기는 순서에 따라 다른 탐색 순서가 나온 것
- A , DCB , HFE, IG 순서로 너비 우선 탐색이 제대로 적용되었다.
정리,
DFS는 깊이 우선 탐색으로 스택(Stack), 재귀호출을 이용해 구현할 수 있다.
BFS는 너비 우선 탐색으로 큐(Queue)를 이용하여 구현할 수 있다.
DFS와 BFS 알고리즘은 다양한 문제를 해결하는데 도움을 준다. (ex. 서로 연결되어 있는 묶음 찾기)