C++ 그래프 탐색 알고리즘 기본 DFS/BFS 구현

이론 : maru20564.tistory.com/6

대표적인 그래프 탐색 알고리즘 DFS/BFS 이론

 

 

Before

 

• 재귀 함수

재귀함수는 함수 내부에서 자기 자신의 함수를 또 호출하는 함수를 의미하며 동작 방식이 스택 자료구조와 비슷하다.

가장 마지막에 실행된 것의 결과가 가장 먼저 나오기 때문이다.

따라서 stack 자료구조를 활용하는 상당수의 알고리즘은 재귀함수를 이용하면 간편하게 구현할 수 있다. ex) DFS 

 

• 그래프 생성

node 개수와 edge 개수, 그 후 edge가 주어졌을 때 해당 그래프를 만드는 코드.

인접리스트 방식을 사용. weight 없음. 단방향 edge.

 

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

int main(void) 
{
    int n, m;
    cin >> n >> m; // node edge의 개수를 입력받음

	//graph 생성
    vector<vector<int>> graph;
    vector<int> edge;
    for (int i = 0; i < n + 1; i++)	//index 0은 사용 안함. node 번호 1부터 시작.
    	graph.push_back(edge);

	//edge 입력
    for (int i = 0; i < m; i++) {
        int u, v;
        //scanf("%d %d", &u, &v);
        cin >> u >> v;
        graph[u].push_back(v);
        //graph[v].push_back(u);    //이 경우는 양방향일 때
    }
    
    return 0;
}

 

인접행렬은 weight[n][n] 크기의 0으로 초기화된 matrix를 만들어 [i][j] 위치에 1(weight 있을 시 weight 값)을 입력하면 된다.

+) edge 입력 시 이미 있는 중복 edge인 경우 예외처리를 넣어주면 좋다. 

 

• 그래프 확인

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

int main(void) 
{
	vector<int> w[6]; //index 0은 사용 안 함 총 node는 5개
	w[1].push_back(3); //1 - 3
	w[1].push_back(5); //1 - 5
	w[2].push_back(3); //2 - 3
	w[3].push_back(4); //3 - 4
	w[4].push_back(5); //4 - 5
	
	//node에 연결된 모든 node 출력
    for(int i = 1; i < 6; i++){
    	cout << i << " - ";
    	for (auto iter = w[i].begin(); iter != w[i].end(); iter++)
			cout << *iter << " ";	//ex node 1의 결과 3 5
        cout << endl;
    }
	
	return 0;
}

 

첫번째 코드에 edge를 그대로 입력하여 출력하는 함수를 추가하면 똑같은 결과가 나타난다.

 

 

 

DFS

 

• 재귀함수 사용

양방향. weight 없음. 인접 node가 여러 개 있을 시 숫자가 작은 순부터 탐색.

 

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

void dfs(int start, vector<vector<int>> graph, bool check[]) 
{
	check[start] = true;	//시작 노드 방문
	cout << start << " ";
	
	for (int i = 0; i < graph[start].size(); i++) {
		int next = graph[start][i];		//인접한 노드 탐색
		if (check[next] == false) {
			//방문하지 않았다면 재귀함수 호출
			dfs(next, graph, check);
		}
	}
}


int main(void)
{
	int n, m, start;
	cin >> n >> m; // node edge의 개수를 입력받음

	//graph 생성
	vector<vector<int>> graph;
	vector<int> edge;
	for (int i = 0; i < n + 1; i++)	//index 0은 사용 안함. node 번호 1부터 시작.
		graph.push_back(edge);

	bool* check = new bool[n + 1];		//탐색 여부를 나타내는 배열
	for (int i = 0; i < n + 1; i++)
		check[i] = false;

	//edge 입력
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);    //양방향
	}

	//탐색을 node 순서대로 할 경우 사용. algorithm 헤더의 sort or 정렬함수 만들어서 사용
	for (int i = 1; i < n + 1; i++)
		sort(graph[i].begin(), graph[i].end());

	//start
	cout << endl << "start node : ";
	cin >> start;
	dfs(start, graph, check);

	return 0;
}

 

• Stack 사용

#include <stack> 에 있는 Stack 사용. main 함수 위와 같음. 

 

void dfs(int start, vector<vector<int>> graph, bool check[]) 
{
	stack<int> dfs_s;
	dfs_s.push(start);		//시작 노드 stack에 삽입
	check[start] = true;	//시작 노드 방문
	cout << start << " ";

	while (!dfs_s.empty()) {
		int current = dfs_s.top();		//현재 위치의 노드
		dfs_s.pop();

		for (int i = 0; i < graph[current].size(); i++) {
			int next = graph[current][i];

			//DFS의 동작 : 인접노드에서 방문하지 않는 노드일 경우 stack에 넣어준다.
			if (check[next] == false) {
				cout << next << " ";
				check[next] = true;
				//pop()을 했었기 때문에 현재 current도 다시 넣어줘야한다.
				dfs_s.push(current);
				dfs_s.push(next);
				break;		//다음 current가 stack의 최상단 노드, 즉 이번에 방문한 노드가 된다.
			}
		}
	}
}

 

- 입력 예시 및 결과

DFS 완전 탐색 결과

 

 

 

BFS

 

#include <queue> 에 있는 Queue 사용. 조건 DFS와 같음. main 함수 탐색 함수를 bfs로 불러오는 것 빼고 같음.

 

void bfs(int start, vector<vector<int>> graph, bool check[]) 
{
	queue<int> bfs_q;

	bfs_q.push(start);			//시작 노드 queue에 삽입
	check[start] = true;		//시작 노드 방문

	while (!bfs_q.empty()) {
		int current = bfs_q.front();
		bfs_q.pop();
		cout << current << " ";

		for (int i = 0; i < graph[current].size(); i++) {
			//현재 노드에서 방문하지 않은 모든 인접한 노드를 queue에 넣고 방문한다.
			if (check[graph[current][i]] == false) {
				bfs_q.push(graph[current][i]);
				check[graph[current][i]] = true;
			}
		}
	}
}

 

- 입력 예시 및 결과

BFS 완전 탐색 결과

 

*예시 그래프 그림은 '이것이 바로 코딩 테스트다 with 파이썬'에서 가져옴.