DFS(깊이 우선 탐색) 알고리즘

DFS(Depth-First Search)란??

DFS는 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 정점으로 되돌아와서 다른 방향으로 진행하는

그래프 순회 방법이다. 그래프 순회 방법에는 대표적으로 DFS와 BFS가 있다. 

 

DFS 예시 - 출처: wikipedia

 

---

 

DFS 이해하기

 

DFS 알고리즘을 구현하는 방법에는 인접 리스트를 이용하는 방법, 인접 행렬을 이용한 방법이 있는데 각각 장단점이 존재한다.

 

인접리스트를 이용했을 때

장점: 모든 노드를 순환하려 할 때 O(N)시간 밖에 걸리지 않는다. 빈 공간이 생기지 않는다.

단점: 인접한 특정 노드를 알고싶을 때 리스트 안에 일일이 찾아봐야한다.

 

인접 행렬을 이용했을 때

장점: 인접한 특정 노드를 알고싶을 때 2차원 배열에 정보가 저장돼있기 때문에 한 번에 찾을 수 있다.

단점: 모든 노드를 순환하려 할 때 O(N^2)시간이 걸린다. 빈 공간이 많이 남을 수도 있다.

 

 

어떤 그래프냐에 따라 리스트를 사용할 지, 행렬을 사용할 지 선택하면 된다.

---

두 방법 모두 전체적인 과정은 이러하다.

1. 출발 노드를 지정한다.

2. 현재 노드를 방문 처리해준 후 인접한 노드들 중 방문하지 않은 노드가 있다면 그 노드로 이동한다.

3. 2번을 반복한다.

4. 방문하진 않았지만 인접한 노드가 아닐 경우 인접한 계속해서 직전 노드로 되돌아간다.

5.다시 2번을 반복한다.

 

---

 

먼저 인접 행렬을 어떻게 이용하는 지 알아보자

인접 행렬을 이용

그래프 예시(노드 간 양방향 연결)

 

위와 같은 그래프의 관계를 인접행렬(2차원 배열)로 나타내면

 

양방향으로 연결되어 있으므로 대각선을 기준으로 대칭인 것을 볼 수 있다.

 

#include<iostream>
#include<vector>
using namespace std;

int adjArray[11][11]; //10*10행렬 생성
int visited[11]; //1~10노드 방문 여부 배열

void AddEdge(int start, int end) { //입력 할 때 양방향으로 저장하는 함수
	adjArray[start][end]=1;
	adjArray[end][start]=1;
}

void DFS(int v) { //DFS
	visited[v]= 1; //방문했다고 표시
    cout << v << ' '; //방문한 노드 출력
	for (int i = 1; i <= 10; i++) { //1~10노드 탐색
		if (adjArray[v][i] == 1 && visited[i]==0) { //현재 노드와 연결된 노드를 1부터 10까지 일일이 탐색
			DFS(i); //위 조건에 만족한 노드가 있다면 DFS함수에 넣기
		}
	}
}

int main() {
    int n=10; //노드 개수

	//노드 관계 저장
    AddEdge(1,3);
    AddEdge(1,7);
    AddEdge(1,8);
    AddEdge(2,3);
    AddEdge(4,5);
    AddEdge(4,10);
    AddEdge(5,8);
    AddEdge(6,8);
    AddEdge(6,9);

	//8노드부터 탐색
    DFS(8);
    
    //그래프를 순회하다가 방문하지 못한 노드가 있다면 DFS 넣기
	for (int v = 1; v <= n; v++) {
		if (visited[v] == 0) {
			DFS(v);
		}
	}
    
}

출력:

방문 순서 출력 - 인접 행렬

 

---

인접 리스트를 이용

 

그래프를 인접 리스트로 표현

 

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int> > adjArray; //이중 벡터 생성
vector<int> visited; //방문 여부 표시 벡터

void AddEdge(int start, int end) { //입력할 때 자동으로 양방향으로 저장할 수 있게 하는 함수
	adjArray[start].push_back(end);
	adjArray[end].push_back(start);
}

void DFS(int v) {
	visited[v] = 1;
	for (int i = 0; i < adjArray[v].size(); i++) { ///인접한 리스트가 끝날 때까지 반복
		int x = adjArray[v][i]; //인접한 노드를 변수 x에 저장
		if (visited[x] == 0) { //노드x가 방문되지 않았다면
			DFS(x); //DFS에 넣기
		}
	}
}

int main() {
    int n=10; //노드 개수
   
   //인접리스트와 방문여부 벡터 초기화
	adjArray.resize(n + 1);
	visited.resize(n + 1);
	
    //인접리스트에 노드 정보 저장
    AddEdge(1,3);
    AddEdge(1,7);
    AddEdge(1,8);
    AddEdge(2,3);
    AddEdge(4,5);
    AddEdge(4,10);
    AddEdge(5,8);
    AddEdge(6,8);
    AddEdge(6,9);

	for (int v = 1; v <= n; v++) {
		if (visited[v] == 0) {
			DFS(v);
		}
	
	}
    
}

 

출력

 

방문 순서 출력 - 인접 리스트

 

---

인접 행렬과 인접 리스트의 노드 방문 순서가 같은 것을 알 수 있다.

그 뜻은 노드 관계 정보를 어떤 식으로 저장하냐에 대한 차이만 있다.