[알고리즘] DFS c++ 구현 및 설명

목차

 

 

dfs의 정의 및 특징

루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말한다.

그래프의 정점을 발견하는 가장 단순하고 고전적인 방법이다.

bfs보다는 비교적 구현이 간단하다.

 

 

 

 

dfs 구현 시 시간 복잡도

• 인접 리스트: O(V +E)

1

2

3

4

3

4

2

3

4

5

1

 

이런식으로 각 노드마다 길이가 달라  O(V +E)시간이 걸린다.

희소한 그래프일 시 추천하는 방법이다.

 

• 인접 행렬: O(V^2)

x	1	2	3	4	5
1	1	1	1	1	1
2	0	1	1	0	1
3	0	0	1	1	0
4	0	1	0	1	1
5	1	0	0	1	1

 

이런식으로 노드의 관계를 나타내 주어 O(V^2) 시간이 걸린다.

조밀한 그래프일 시 추천하는 방법이다.

 

 

dfs의 구현

나는 재귀적인 방법을 이용한 구현과 스택을 이용한 구현 둘 다 해보았다.

또한 시간 복잡도가 낮은 인접리스트로 구현 해 보았다.

 

 

 

 

재귀호출을 이용한 구현

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

//인접 리스트 사용 및 재귀적 호출 방법
bool visited<9, false>; 
vector<int> graph[9];

void dfs(int x)
{
	visited[x] = true;
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
	{
		int y = graph[x][i];
		if (!visited[y]) // 방문하지 않았으면 
            dfs(y); // 재귀적으로 방문
	}
}

int main(void)
{
    /* 위 그래프와 동일하게 정의 */
    graph[1].push_back(2);
    graph[2].push_back(1);
    
    graph[2].push_back(3);
    graph[3].push_back(2);
    
    graph[1].push_back(5);
    graph[5].push_back(1);
    
    graph[5].push_back(2);
    graph[2].push_back(5);
    
    graph[5].push_back(6);
    graph[6].push_back(5);
 
    dfs(1);

 

재귀호출 이용 구현 설명

 

 

 

 

 

 

 

 

 

• 1 -> 탐색 시작
• 1 -> 2 방문하지 않았으므로 재귀 호출
• 1 -> 2 -> 3 방문하지 않았으므로 재귀 호출
• 3은 더 이상 탐색 불가하므로 2에서 탐색 시작
• 2 ->5 방문하지 않았으므로 재귀 호출
• 5 -> 6 방문하지 않았으므로 재귀 호출
• 6은 더 이상 탐색 불가
• 모든 곳 방문으로 종료

 

 

 

 

스택을 이용한 구현

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

vector<int>graph[1000];
vector<bool>visit(1000, false);

void dfs(int start) {
	stack<int> s;
	int i;
	s.push(start);
	visit[start] = true;
	cout << start;
	while (!s.empty()) {   //스택이 빌 때까지 반복 해 준다. 
		int del = 1;  //인접한 노드 확인용
		int x = s.top();
		
		for (i = 0; i < graph[x].size(); i++) {
			if (!visit[graph[x][i]]) {  //방문하지 않았다면 스택에 넣어준다.
				
				cout << graph[x][i];
                
                s.push(graph[x][i]);
				visit[graph[x][i]] = true;
				del = 0;
				break;
			}
		
		}
		if (del) {  //인접한 노드가 아예 없는 경우 삭제 해 준다.
			s.pop();
		}
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    graph[1].push_back(2);
    graph[2].push_back(1);
    
    graph[2].push_back(3);
    graph[3].push_back(2);
    
    graph[1].push_back(5);
    graph[5].push_back(1);
    
    graph[5].push_back(2);
    graph[2].push_back(5);
    
    graph[5].push_back(6);
    graph[6].push_back(5);
 
    dfs(1);
}

 

 

스택 이용 구현 설명

 

 

 

 

 

 

 

 

 

 

1

 

• 1 방문했으므로 스택에 넣기

 

2

1

 

• 2 방문했으므로 스택에 넣기

 

3

2

1

 

• 3 방문했으므로 스택에 넣기

2

1

 

• 방문할 노드가 있는 곳이 나올 때까지 pop해 준다.

 

5

2

1

 

• 2 ->5 로 방문했으니 스택에 넣기

 

6

5

2

1

 

• 6 방문했으므로 스택에 넣기

 

.

.

.

 

 

• 방문할 노드가 생길때 까지 pop해 주면 스택이 다 비워진다.

 

 

참고

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체