<algorithm> 깊이 우선 탐색(DFS)

- DFS란, 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동하는 방법이다.

- 시작 노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드로 돌아가서, 다시 깊이우선 탐색을 반복

- 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법

https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif#

 

stack 또는 recursive(재귀 함수)로 구현.

 

1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 수행할 수 없을 때까지 반복

 

 

 

 

 

 

- 노드 방문 시 방문(visited) 여부를 반드시 검사해야 한다. 아니면 무한 루프에 빠질 수 있음.

 

- 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)를 사용.

 

- 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노두의 부모노드로 돌아와서(백트래킹-backtracking), 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성.

 

- 시간 복잡도(Time complexity) : 인접 리스트로 구현 시 O(V+E) // 인접 행렬로 구현 시 O(V^2)

 

- 재귀 함수로 구현 시, 별도의 자료구조가 필요하지 않으므로 메모리를 아낄 수 있다.

  (BFS의 경우 queue를 사용해야 하므로 DFS에 비해 메모리를 더 사용할 수 밖에 없다.)

 

- 얻은 결과가 최단 경로라는 보장이 없다. (반면, BFS는 얻은 결과가 최단 경로이다.)

 

 

 

https://www.youtube.com/watch?v=M48Po-wTOpU

<입력>

5 6

0 1 0 2 1 3 1 4 2 4 3 4 

 

<recursive dfs출력> 

0 1 3 4 2

<stack dfs 출력>

0 2 4 3 1

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

// recursive DFS
#define MAX_N 10
int N, E; //N: 정점의 수 E: 엣지의 수
int Graph[MAX_N][MAX_N];
bool Visited[MAX_N];

int main(){
	cin>>N>>E;
    memset(Visited, 0, sizeof(Visited));
    memset(Graph, 0, sizeof(Graph));
    for( int i=0; i<E; ++i){
    	int u,v;
        cin >> u >> v;
        Graph[u][v] = Graph[v][u] =1; // u에서 v로 이동가능, 역도 성립
     }
     dfs(0);
     return 0;
 }

void dfs(int node){
	Visited[node] = true; //node번째 node를 방문했다.
    cout << node << ' ';
    
    for(int next = 0 ; next < N; ++next){
		if(!Visited[next] && Graph[node][next]) //방문이 되어있지 않고, 간선(엣지)이 있다면
        	dfs(next);
    }
}

 

재귀호출을 너무 많이하게 되면 stack overflow 의 우려가 있다. GLOBAL 변수사용하는 이유

 

DFS - STACK 구현

 

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;

// STACK DFS

#define MAX_N 10
int N,E;
int Graph[MAX_N][MAX_N];

int main(){
	cin>>N>>E;
    memset(Graph, 0, sizeof(Graph));
    
    for(int i =0; i<E; ++i){
    	int u,v;
        cin >> u >> v; 
        Graph[u][v] = Graph[v][u] =1;
    }
    dfs(0);
    return 0;
 }

 

void dfs(int node){
	bool visited[MAX_N] = {false}; //선언과 동시 초기화 
    
    stack<int> mystack;
    mystack.push(node); //시작노드 push
    
    while(!mystack.empty()){
    	int curr = mystack.top();
        mystack.pop();
        
        if(visited[curr]) continue; // 현재노드가 방문된 곳이라면? continue;
        
        visited[curr] = true;
        cout << curr << ' ';
        
        for(int next = 0; next <N; ++next){
        	if(!visited[next] && Graph[curr][next])
            	mystack.push(next);
        }
     }
  }

 

출처

https://wannadev.tistory.com/96

BFS, DFS c++