깊이 우선 탐색 (DFS, Depth First Search)

- 그래프를 탐색할 때 쓰는 알고리즘 중 하나

- 어떤 노트부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않는다.

- 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색한다.

cf) 분기 : 2개 이상의 정점으로 쪼개지는 부분

cf) BFS는 level 별로 탐색한다.

 

가장 멀리있는 노드까지 탐색

---

DFS 수도코드

DFS(u, adj)
   u.visited = 1
   for v ∈ adj[u]
      if(v.visited ==0)
         DFS(v, adj)

---

DFS 코드 구현

#include <bits/stdc++.h>
using namespace std;

const int n=6;
vector<int> adj[n];
int visited[n];

void dfs(int u){
	visited[u]=1;
	cout << u << "\n";
	
	for(int v : adj[u]){
		if(visited[v]==0){
			dfs(v);
		}
	}
    cout << u <<"로부터 함수가 종료되었습니다\n";
    return;          //함수종료
}



int main(){
	
	adj[1].push_back(2);
	adj[1].push_back(3);
	adj[2].push_back(4);
	adj[2].push_back(5);
	adj[4].push_back(2);
	
	dfs(1);
		
	return 0;
}

재귀적으로 함수종료

결과값

1
2
4
5
3