한국어로 깊이 우선 탐색으로 그래프를 완벽히 탐색한다.
시작지점부터 다음 Branch로 넘어가기 전 해당 Branch를 완벽히 탐색한다.
Vector의 사용
[예시 그래프]
#include<iostream>
#include<vector>
using namespace std;
int check[10];
vector<vector<int> > graph(9);
void dfs(int x)
{
check[x]=1;
printf("%d ", x);
for(int i=0; i<graph[x].size(); i++){
if(check[graph[x][i]]==0){
check[graph[x][i]]=1;
dfs(graph[x][i]);
}
}
}
int main(){
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
graph[2].push_back(1);
graph[2].push_back(7);
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
graph[4].push_back(3);
graph[4].push_back(5);
graph[5].push_back(3);
graph[5].push_back(4);
graph[6].push_back(7);
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
graph[8].push_back(1);
graph[8].push_back(7);
dfs(1);
}
출력 결과 값 : 1 2 7 6 8 3 4 5
시작노드 방문 후 모든 인접한 노드 방문.
더이상 방문하지 않은 노드가 없을 때 까지 방문한다.
[예시 그래프]
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int check[10]
queue<int> q;
vector<vector<int> > graph(9)
void bfs(int x)
{
while(!q.empty()){
int x=q.front();
q.pop();
printf("%d ", x);
for(int i=0; i<graph[x].size(); i++){
if(check[graph[x][i]==0]){
q.push(graph[x][i]);
check[graph[x][i]=1;
}
}
}
}
int main(){
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
graph[2].push_back(1);
graph[2].push_back(7);
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
graph[4].push_back(3);
graph[4].push_back(5);
graph[5].push_back(3);
graph[5].push_back(4);
graph[6].push_back(7);
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
graph[8].push_back(1);
graph[8].push_back(7);
q.push(1);
check[1]=1;
bfs(1);
}
출력 결과 값 : 1 2 3 8 7 4 5 6