6장 그래프 - (3) 그래프의 탐색

1. 그래프의 탐색 

- 목적 : 모든 정점을 1번씩 방문

- DFS : 깊이 우선 탐색, 최대한 깊숙히 많이 방문, 재귀 또는 stack 구현

- BFS : 너비 우선 탐색, 최대한 넓게 많이 방문, queue 구현, 모든 가중치가 1일 때 최단거리 구할 수 있음

2. 깊이 우선 탐색(Depth First Search) 

- 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 (stack에 push)

- 갈 수 없으면 이전 정점으로 돌아간다. (stack에서 pop)

- stack이 비면 탐색 종료

- 재귀 호출을 이용해서도 구현할 수 있다.

(예시 1) - 인접행렬, 재귀 호출

void dfs(int x){

check[x]=true;

printf("%d", x);

for(int i=1;i<=n;i++){

if(a[x][i]==1 && check[i]==false){

dfs(i);

}

}

}

(예시 2) - 인접리스트, 재귀 호출

void dfs(int x){

check[x] = true;

printf("%d ",x);

for(int i=0;i<a[x].size();i++){

int y = a[x][i];

if(check[y]==false)

dfs(y);

}

}

3. 너비 우선 탐색(Breadth First Search)

- 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식

- 큐에 넣을 때 방문했다고  체크

(예시 1) - 인접 행렬, Queue 사용

queue<int> q;

check[1]=true, q.push(1); // 큐에 넣을 때 방문했다고 체크

while(!q.empty()){

int x = q.front(); q.pop();

printf("%d ",x);

for(int i=1;i<=n;i++){

if(a[x][i]==1 && check[i]==false){

check[i]=true;

q.push(i);

}

}

}

(예시 2) - 인접 리스트, Queue 사용

queue<int> q;

check[1]=true; q.push(1);

while(!q.empty()){

int x = q.front(); q.pop();

printf("%d ",x);

for(int i=0;i<a[x].size();i++){

int y = a[x][i];

if(check[y]==false){

check[y]=true;

q.push(y);

}

}

}

4. 시간 복잡도

-인접 행렬 : O(V^2)

-인접 리스트 : O(V+E)

5. 문제

-1260번(DFS와 BFS)

#include <iostream>

#include <vector>

#include <queue>

#include <cstring> // memset 함수

#include <algorithm>

using namespace std;

int n, m;

bool check[1001];

vector<int> a[1001];

void dfs(int x) {

check[x] = true;

printf("%d ", x);

for (int i = 0; i < a[x].size(); i++) {

int y = a[x][i];

if (check[y] == false) {

dfs(y); // 방문하지 않은 다음 깊이의 노드 먼저 탐색, 재귀호출

}

}

}

void bfs(int x) {

queue<int> q;

check[x] = true; 

q.push(x);

while (!q.empty()) {

int now = q.front(); q.pop();

        printf("%d ", now);

for (int i = 0; i < a[now].size(); i++) {

int y = a[now][i];

if (check[y] == false) {

check[y] = true;

q.push(y); // 방문하지 않은 다음 너비의 노드 탐색

}

}

}

}

int main(void) {

int s;

cin >> n >> m >> s;

for (int i = 0; i < m; i++) {

int u, v;

scanf("%d %d", &u, &v);

a[u].push_back(v);

        a[v].push_back(u);

}

    for(int i=1;i<=n;i++){

        sort(a[i].begin(),a[i].end()); // 방문할 다음 노드가 여러개인 경우, 숫자가 작은 노드부터 방문하기 위해 미리 오름차순 정렬

    }

dfs(s);

memset(check, false, sizeof(check));

printf("\n");

bfs(s);

printf("\n");

return 0;

}