DFS(깊이 우선 탐색) 알고리즘
DFS(Depth-First Search)란??
DFS는 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 정점으로 되돌아와서 다른 방향으로 진행하는
그래프 순회 방법이다. 그래프 순회 방법에는 대표적으로 DFS와 BFS가 있다.
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);
}
}
}
출력
인접 행렬과 인접 리스트의 노드 방문 순서가 같은 것을 알 수 있다.
그 뜻은 노드 관계 정보를 어떤 식으로 저장하냐에 대한 차이만 있다.