알고리즘/탐색
깊이 우선 탐색(DFS)
Dero Lee
2021. 12. 25. 00:51
728x90
깊이 우선 탐색(Depth First Search) :
탐색을 하는 데 있어 깊은 것을 우선적으로 하여 탐색하는 알고리즘.
스택이 사용되지만, 컴퓨터는 구조적으로 시스템 스택 프레임의 원리를 사용하기때문에 스택을 사용하지 않아도 재귀적으로 구현이 가능함.
- 시작 노드를 스택에 삽입하고, 방문 처리한다.
- 스택의 최상단 노드를 확인한다.
- 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고, 방문처리 한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 뺀다.
- 2, 3의 과정은 스택이 비어질때까지 반복된다.
#include <iostream>
#include <vector>
using namespace std;
int n = 7;
int checked[7];
vector<int> arr[8];
void dfs(int x) {
if(checked[x]) return;
checked[x] = true;
cout<<x<<' ';
for(int i = 0; i<arr[x].size(); i++) {
int y = arr[x][i];
dfs(y);
}
}
int main() {
// 연결된 노드들을 나타내고, 인접 노드도 표현.
arr[1].push_back(2);
arr[2].push_back(1);
arr[1].push_back(3);
arr[3].push_back(1);
arr[2].push_back(3);
arr[3].push_back(2);
arr[2].push_back(4);
arr[4].push_back(2);
arr[2].push_back(5);
arr[5].push_back(2);
arr[3].push_back(6);
arr[6].push_back(3);
arr[3].push_back(7);
arr[7].push_back(3);
arr[4].push_back(5);
arr[5].push_back(4);
arr[6].push_back(7);
arr[7].push_back(6);
dfs(1);
return 0;
}
728x90