개인 공부/알고리즘
[C++] DFS 깊이 우선 탐색 알고리즘
_h.j
2021. 2. 18. 21:32
728x90
깊이 우선 탐색 (Depth - First Search)
개념
DFS(깊이 우선탐색) : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
- 현재 정점에서 다음 분기로 넘어가기 전에 해당 분기를 완변하기 탐색
- 노드를 깊게 탐색
DFS 장점
1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간 수요 비교적 적음
2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음
3. 구현이 BFS보다 간단
DFS 단점
1. 단순 검색 속도는 BFS 보다 느림
2. 사전에 임의의 깊이를 지정 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로 탐색하도록 하는 것이 좋음
3. 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로 , 구한 해가 최단 경로가 된다는 보장이 없음.
(목표에 이르는 경로가 다수인 경우 구한 해가 최적이 아닐 수 있음)
방법
스택 또는 재귀함수로 구현
DFS 소스코드
재귀 방법
#include <bits/stdc++.h>
using namespace std;
const int MAX = 10;
void DFS(int start, vector<int> graph[] , bool check[] ){
check[start]=true;;
cout<< start<<" "; //방문한 정점 출력
for(int i = 0 ; i< graph[start].size();i++){
int next = v[start][i];
if(!check[next]){//방문하지 않았다면 DFS 호출
DFS(next , graph, check);
}
}
}
int main(){
int n,m,start; // 노드 개수 , 간선 개수
cin >> n >> m >> start;
vector<int>graph[n+1];
//visual studio 의 경우
/* 변수 통해 배열 동적 생성 시
vector<int> * g = new vector<int>[n+1];
*/
bool check[n+1]={0,};
for(int i = 0 ; i < m; i++){
int u,v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
//나중에 하나의 정점에서 다음 탐색 시 node 값 순차적으로
//접근하고 싶으면 graph sort 하면 됨
DFS(start,graph,check);
return 0;
}
stack 이용
#include <bits/stdc++.h>
using namespace std;
const int MAX = 10;
//stack에 들어가면 방문한 것으로 판단
//해당 위치를 true로 해준다.
void DFS(int start, vector<int> graph[] , int check[] ){
stack<int> s;
s.push(start);
check[start]++;
cout << start <<" ";
while( !s.empty() ){
int current = s.top();
s.pop();
for(int i = 0 ; i < graph[current].size() ; i++){
int next = graph[current][i];
if(!check[next]){
cout<<next<<" ";
check[next]++;
s.push(current);//current로 다시 push 해야함.
s.push(next);
break;//너비가 아니라 깊이 우선이라
}
}
}
}
int main(){
int n,m,start; // 노드 개수 , 간선 개수
cin >> n >> m >> start;
vector<int>graph[n+1];
//visual studio 의 경우
/* 변수 통해 배열 동적 생성 시
vector<int> * g = new vector<int>[n+1];
*/
int check[n+1]={0,};
for(int i = 0 ; i < m; i++){
int u,v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
//나중에 하나의 정점에서 다음 탐색 시 node 값 순차적으로
//접근하고 싶으면 graph sort 하면 됨
DFS(start,graph,check);
return 0;
}구현할 때 출력 어디서 해야하는지 생각하기
노드 개수가 많을 땐 visit bool로 하기!!
참고
728x90