[알고리즘] C++로 DFS와 BFS 구현

 

C++로 DFS와 BFS 구현

사용할 예제

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Vertex {
	// 데이터
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
//dfs 방문 여부
vector<bool> visited;
//bfs 발견 여부
vector<bool> discovered;

void CreateGraph() {
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	adjacent[0].push_back(1);
	adjacent[0].push_back(3);
	adjacent[1].push_back(0);
	adjacent[1].push_back(2);
	adjacent[1].push_back(3);
	adjacent[3].push_back(4);
	adjacent[5].push_back(4);
}

 

 

DFS란

* edge로 연결되어 있는 정점끼리만 이동가능하다.

 

* edge가 여러 개라면 어떤 기준으로 탐색하는가?

  >> 아무곳이나 전부

 

* 아무곳이나 탐색하다가 이미 왔던 곳이면 가지 않는다. 

 

* 재귀 함수로 만든다면?

  1. 현재 정점 방문 체크

  2. 연결된 edge 찾기

  3. 연결된 정점이 방문했는지 체크

      (방문 했던 곳이면 들어가지 않는다.)

  4. 방문하지 않은 정점으로 재귀함수 실행

 

 

C++로 DFS 구현

// DFS = 깊게 들어가는 탐색
// 보통 재귀함수로 만들다.
// 재귀함수 기능 = 인접 정점을 탐색한다.  처음 보는 정점이면 해당 정점으로 재귀 실행
// here = 시작 위치
// 중복 탐색을 방지하기 위해 지나간 정점 저장
void Dfs(int here) {
	// 시작 위치 방문 체크
	visited[here] = true;
	cout << "Visited : " << here << endl;
	
	// 모든 인접 정점 순회
	for (int i = 0; i < adjacent[here].size(); i++) {
		int there = adjacent[here][i];
		// 처음 보는 정점이면 재귀
		if (visited[there] == false) {
			Dfs(there);
		}
	}
}

// 모든 정점을 탐색하는 함수
// 여기서 한번더 중복 체크를 하므로 불필요한 함수 호출을 막음
// edge가 전혀 없는 정점도 찾을 수 있다.
void DfsAll() {
	visited = vector<bool>(6, false);

	for (int i = 0; i < 6; i++) {
		if (visited[i] == false) {
			Dfs(i);
		}
	}
}

int main(){
	CreateGraph();
	DfsAll();
}

* 해당 정점의 방문 여부를 저장하기 위해 

  vector<bool> visited을 생성

 

 

BFS란

* edge로 연결되어 있는 정점끼리만 이동가능하다.

 

* edge가 여러개라면 어떤 기준으로 탐색하는가?

  >> 아무곳이나 전부

 

* 아무곳이나 탐색하다가 이미 왔던 곳이면 가지 않는다. 

 

* 정점을 찾아도 바로 실행하는 것이 아니라  Queue에 저장

  >> 나중에 들어간 정점이 나중에 처리된다.

 

* 큐를 사용하기 때문에 

  가장 근접한 정점이 모두 처리되고,

  그 다음 정점들이 실행된다.

 

* 가장 가까운 정점부터 실행하기 때문에

  무조건 최단거리로 탐색하게 된다.

 

 

C++로 BFS 구현

// BFS (길찾기에서 유용)
// queue를 사용, 깊은 정점을 찾지만 queue에 넣고 나중에 사용
//
void Bfs(int here){
    vector<int> parent(6, -1);
    vector<int> distance(6, -1);
    
    parent[here] = here;
    distance[here] = 0;
    
    queue<int> q;
    q.push(here);
    discovered[here] = true;
    
    while(q.empty() == false){
        here = q.front();
        q.pop(); // pop은 반환이 없구나?
        cout << "Visited : " << here << endl;
        
        for(int there : adjacent[here]){
            if(discovered[there] == true){
                continue;
            }
            discovered[there] = true;
            q.push(there);
            
            distance[there] = distance[here] + 1;
            parent[there] = here;
        }
    }
}

void BfsAll(){
    for(int i =0;i<6;i++){
        if(discovered[i] == false)
            Bfs(i);
    }
}

int main(void) {
    CreateGraph();
    
    discovered = vector<bool>(6, false);
    BfsAll();
}

* 해당 정점이 이미 Queue에 들어갔는지 확인하기 위해

  vector<bool> discoverd를 사용

 

 

 

 

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.