9. DFS(깊이 우선 탐색)
DFS(깊이 우선 탐색)
DFS는 깊이 우선 탐색을 뜻합니다. 이 DFS 또한 맹목적으로 각 노드를 탐색할 때 주로 사용됩니다. DFS는 자료구조로 stack을 사용해서 구현됩니다. 하지만 사실 스택을 안쓰고 재귀함수로도 구현이 가능합니다. 이유는 컴퓨터 자체가 구조적으로 항상 스택의 원리를 이용하기 때문입니다.
DFS 과정
- 시작 노드 스택에 삽입
- 시작 노드 방문 처리
- 스택 최상단 노드 확인
- 최상단 노드에 방문 하지 않은 인접 노드 있으면 그 노드를 스택에 넣고 방문 처리 / 없으면 최상단 노드 빼기
- 3,4번 과정을 스택이 빌 때까지 반복
#include <iostream>
#include <vector>
using namespace std;
int number = 7;
int visited[8];
vector<int> a[8];
void dfs(int x) {
if (visited[x]) return;
visited[x] = true;
cout << x << " ";
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
dfs(y);
}
}
int main() {
a[1].push_back(2);
a[1].push_back(3);
a[2].push_back(1);
a[2].push_back(3);
a[2].push_back(4);
a[2].push_back(5);
a[3].push_back(1);
a[3].push_back(2);
a[3].push_back(6);
a[3].push_back(7);
a[4].push_back(2);
a[4].push_back(5);
a[5].push_back(2);
a[5].push_back(4);
a[6].push_back(3);
a[6].push_back(7);
a[7].push_back(3);
a[7].push_back(6);
dfs(1);
return 0;
}
Author And Source
이 문제에 관하여(9. DFS(깊이 우선 탐색)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@l0_0l/9.-DFS깊이-우선-탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)