[Algorithm] C++에서 그래프 탐색(DFS와 BFS) 구현하기

업데이트(2019.03.02) : DFS, BFS 이미지 추가

업데이트(2018.04.07) : Stack을 이용한 DFS 방식 추가

C++에서 그래프 탐색(DFS와 BFS)을 구현하는 방법을 알아보자.


환경 및 선수조건


탐색

개념

dfs-bfs-example

  • DFS(깊이우선탐색) : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
  • BFS(너비우선탐색) : 현재 정점에 연결된 가까운 점들부터 탐색
  • 위의 이미지를 참고하시면 비교가 쉽습니다. 해당 번호 순서대로 탐색을 합니다.

방법

  • DFS : 스택 또는 재귀함수로 구현
  • BFS : 큐를 이용해서 구현


구현

  • List(여기서는 vector)를 통해서 구현
  • https://www.acmicpc.net/problem/1260 풀이와 관련된 구현
  • graph[] : List를 통해서 구현한 그래프
  • check[] : 탐색을 했으면 true 아니면 false로 구분

DFS

Recursion 이용

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

// dfs에 들어오면 '방문'한거로 판단
// 해당 위치에 check true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){
	check[start]= true;
	printf("%d ", 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 (){

	int n, m, start;
	cin >> n >> m >> start;

	vector<int> graph[n+1];
	bool check [n+1];
	fill(check, check+n+1, false);

	for(int i=0; i<m; i++){
		int u,v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// Sorting은 왜 한거지?
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for(int i=1; i<=n; i++){
		sort(graph[i].begin(), graph[i].end());
	}

	//dfs
	dfs(start, graph, check);
	printf("\n");

	return 0;
}

Stack 이용

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>

using namespace std;


// stack에 들어가면 방문한거로 판단
// 해당 위치를 true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){

	stack<int> s;
	s.push(start);
	check[start] = true;
	printf("%d ",start);

	while(!s.empty()){

		int current_node = s.top();
		s.pop();
		for(int i=0; i<graph[current_node].size(); i++){

			int next_node = graph[current_node][i];

			if(check[next_node]==false){
				printf("%d ", next_node);
				check[next_node] = true;
				// pop()을 했었기 때문에 현재 current_node도 넣어줘야한다.
				s.push(current_node);
				s.push(next_node);
				break;
			}
		}
	}

}

int main (){


	int n, m, start;
	cin >> n >> m >> start;

	vector<int> graph[n+1];
	bool check [n+1];
	fill(check, check+n+1, false);

	for(int i=0; i<m; i++){
		int u,v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// Sorting은 왜 한거지?
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for(int i=1; i<=n; i++){
		sort(graph[i].begin(), graph[i].end());
	}

	//dfs
	dfs(start, graph, check);
	printf("\n");

	return 0;
}


BFS

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

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

	while(!q.empty()){
		int tmp = q.front();
		q.pop();
		printf("%d ",tmp);
		for(int i=0; i<graph[tmp].size(); i++){

			// 방문하지 않았다면
			if(check[graph[tmp][i]] == false){
				// 큐에 넣어주고 방문했음을 표시한다.
				q.push(graph[tmp][i]);
				check[graph[tmp][i]] = true;
			}
		}
	}

}

int main (){

	int n, m, start;
	cin >> n >> m >> start;

	vector<int> graph[n+1];
	bool check [n+1];
	fill(check, check+n+1, false);

	for(int i=0; i<m; i++){
		int u,v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// Sorting은 왜 한거지?
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for(int i=1; i<=n; i++){
		sort(graph[i].begin(), graph[i].end());
	}

	//bfs
	bfs(start, graph, check);
	printf("\n");

	return 0;
}


참고자료

[Linux] 쉘 스크립트에서 멀티프로세스(혹은 스레드) 기능 사용하기

> 백그라운드로 명령어를 실행해서 병렬적으로 실행되는 멀티 프로세스 환경을 만들어보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)## 멀티프로세스? 병렬처리? 멀티스레드? 백그라운드 프로세스?- 여기서 진행할 방식...… Continue reading