BFS, DFS c++

- 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);
        }
     }
  }

 

 

 

너비 우선 탐색(BFS, Breadth-First Search)

- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

- 큐를 사용하여 구현됨

1. A 노드(시작 노드)를 방문한다. (방문한 노드 체크)
   - 큐에 방문된 노드를 삽입(enqueue)한다.
   - 초기 상태의 큐에는 시작 노드만이 저장 (초기 큐에서는 시작 노드만 있음)
         - 즉, A 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
2. 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
   - 큐에서 꺼낸 노드를 방문한다. (큐에서 값을 빼서 탐색 시작)
   - 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
   - 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
   - 큐에 방문된 노드를 삽입(enqueue)한다.
3. 큐가 소진될 때까지 계속한다.

breadth_first_search(v):

v를 방문되었다고 표시;
큐 Q에 정점 v를 삽입;
while (Q가 공백이 아니면) do 
	Q에서 정점 w를 삭제;
	for all u ∈ (w에 인접한 정점) do 
		if (u가 아직 방문되지 않았으면)
			then u를 큐에 삽입;
				u를 방문되었다고 표시;

 

C++ 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool visited[9];
vector<int> graph[9];

// BFS 함수 정의
void bfs(int start) {
    queue<int> q;
    q.push(start); // 첫 노드를 queue에 삽입
    visited[start] = true; // 첫 노드를 방문 처리

    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void) {
    // 노드 1에 연결된 노드 정보 저장 
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);

    bfs(1);
}

출력

1 2 3 8 7 4 5 6

 

너비 우선 탐색(BFS)의 시간 복잡도
- 인접 리스트로 표현된 그래프: O(N+E)
- 인접 행렬로 표현된 그래프: O(N^2)

 

https://hanseongbugi2study.tistory.com/36

<algorithm> 너비 우선 탐색(BFS)

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

 

출처 : 

https://m42-orion.tistory.com/63

[C++ Algorithm] Graph - DFS : Depth-First Search (깊이 우선 탐색)

 

출처 : 

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

DFS & BFS 이해하기 및 구현(C++)