[C++] BFS와 DFS

친구가 기초 알고리즘 과외를 한다고 하는게 갑자기 생각남.

1, 2 강의에 BFS, DFS 기초 탐색 및 응용

3 강의에 DP

4 강의에 다익스트라

내 생각에는 날로 쳐먹으려는게 확실함

그냥 갑자기 생각나서 예전 기억 더듬으며 위 내용 복습 해보려고함.

BFS ? 

너비 우선 탐색

1) 시작 노드에서 자신의 자식 노드들을 모두 방문

2) 방문한 자식 노드 순서대로 1) 과정을 반복

DFS ? 

깊이 우선 탐색

1) 시작 노드에서 자식 노드 중 1개를 방문

2) 방문한 자식 노드에서 1)을 반복 (만약 방문했었던 노드일 경우 재방문 안함)

3) 현재 노드에서 더 이상 방문할 노드가 없을 경우 부모 노드로 이동-> 1)반복

예제를 들어 보면..

C++ 구현해보자

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

#include<bits/stdc++.h> using namespace std; int n,m,v; bool visit[1005]; vector<int> path[1005]; queue<int> q;   void dfs(int v){     for(int i=0;i<path[v].size();++i){         if(!visit[path[v][i]]){             visit[path[v][i]]=1;             printf("%d ",path[v][i]);             dfs(path[v][i]);         }     } } void bfs(int v){     for(int i=0;i<path[v].size();++i){         if(!visit[path[v][i]]){             q.push(path[v][i]);             visit[path[v][i]]=1;         }     }     while(!q.empty()){         int t = q.front();         q.pop();         printf("%d ",t);         bfs(t);     } } int main(){     int x,y;     scanf("%d%d%d",&n,&m,&v);     for(int i=0;i<m;++i){         scanf("%d%d",&x,&y);         path[x].push_back(y);         path[y].push_back(x);     }     for(int i=0;i<n;++i)         sort(path[i].begin(),path[i].end());     visit[v]=1;     printf("%d ",v);     dfs(v);     puts("");     memset(visit,0,sizeof(visit));     visit[v]=1;     printf("%d ",v);     bfs(v); }