BFS vs DFS | 자료구조실습 9주차 과제

* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다

 

 

0. 그래프 개념

 

그래프 표기

G = (V, E)

- G: 그래프

- V: 정점의 집합

- E: 간선의 집합

 

Directed 그래프

- 방향이 있는 그래프

- 표기: (1, 2) -> 1이 2를 가리킴

- (1,2) 와 (2,1)은 다름

 

표기

V = {a, b, c}

E = {(a,c), (b,a), (b,c), (c,b)}

 

 

Undirected 그래프

- 방향이 없는 그래프

- 표기: {1, 2} -> 1과 2가 서로 연결됨

- {1, 2}와 {2, 1}은 같음

 

표기

- V = {a, b, c ,b}

- E = {{a,b}, {a,c}, {b,c}, {c,d}, {a,d}}

 

 

 

 

 

 

1. BFS와 DFS란 무엇인가?

 

BFS

: 너비 우선 탐색

- 인접한 노드부터 탐색하는 방식

- 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점은 나중에 방문함

 

: 장단점

- 장점: 최단 경로를 보장함

- 단점: 경로가 다양한 경우 많은 메모리를 필요로 함

 

: 사용

- 최단 경로 탐색, 웹 크롤링, 소셜 네트워킹, Garbage collection(메모리 접근)

- model check, 수학적 검증, solving puzzle game 등

 

: 알고리즘 접근

1)  Adj (인접 리스트, Adjacency List)

 

- 정점(V)과 연결되어 있는 특정 정점들이 무엇인지 저장하는 저장소

 

    예를 들어, b가 a, c를 가리킨다고 할 경우

    이렇게 표시할 수 있다

 

 

- 전체 예시

 

이런 식으로 정점들이 서로 어떻게 연결되어 있는지 알 수 있다!

 

2) Queue 사용

- 선입선출(FIFO) 원칙으로 탐색을 진행하게 된다

- 먼저, 정점과 인접한 특정 정점들을 모두 삽입한다

- 그후, 가장 앞에 있는 정점부터 pop을 하는데, 만약 해당 정점과 연결된, 아직 방문하지 않은 정점이 존재할 경우 이를 last에 삽입해준다

- queue가 empty할 때까지 반복한다

 

3) Visited

- BFS는 모든 정점을 "한 번씩" 방문하기 때문에, 한 번 방문했던 노드는 다시 방문하지 않도록 설정해야 함

- Visited라는 bool type의 배열을 선언하여 방문 여부를 체크해야 함

=> vector를 사용해 방문여부 체크

 

 

DFS

: 깊이 우선 탐색

- 최대한 깊게 내려간 후, 더 이상 내려갈 곳이 없을 경우 옆으로 이동하는 방식

 

: 장단점

- 장점: 구현이 비교적 쉬움, 모든 경로를 방문하고자 할 때 주로 사용, BFS보다 적은 메모리 사용

- 단점: 최단 경로라는 보장이 없음, 최악의 경우 해에 도달하는 시간이 가장 오래 걸림

 

: 사용

- 미로 탐색 (최대한 한 방향으로 쭉 가다가, 길이 막힐 경우 다음 방향을 찾아 다시 탐색) 등

 

: 알고리즘 접근

1) Adj (인접 리스트)

- BFS와 같이 정점(V)과 연결되어 있는 특정 정점들이 무엇인지 저장하는 저장소를 만든다

 

2) Stack 사용

- 먼저, 현재 정점과 인접한 정점들을 stack에 넣는다

- 그 후, stack에 마지막으로 삽입된 정점에서 더이상 탐색할 정점이 없을 경우 이를 pop한다

- stack이 empty할 때까지 과정 반복

 

3) Visited

- BFS와 같이 Visited 배열을 사용하여 정점의 방문 여부를 파악한다

=> vector를 사용해 방문 여부 체크

 

 

 

 

 

2. 그래프 예시

 

1 ~ 9번까지의 가게와 이를 이어주는 길을 정점과 간선으로 표시

 

 

 

 

 

3. BFS와 DFS를 이용한 그래프 탐색 과정

 

BFS 탐색

 

- Queue 사용

 

DFS 탐색

 

- Stack 사용

 

* 중요: Visited도 항상 검사해야 함!

 

 

 

4. BFS와 DFS 구현 코드

 

혼자 코드 짜는게 너무 어려워서으억... 일단 교수님께서 알려주신 코드를 참고하여 작성해보았다.

 

 

BFS와 DFS 구현

 

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

class Graph {
private:
	int data;
	int vertices; // 정점 갯수
	bool* visited; // 방문 여부
	vector<list<int>> adj; // 연결된 정점 정보

public:
	Graph(int _vertices) {
		vertices = _vertices; // 정점 갯수 초기화
		visited = new bool[_vertices];
		for (int i = 0; i < _vertices; i++) {
			visited[i] = false;
		}
		adj.resize(_vertices);
	}

	~Graph() {
		delete visited;
	}

	void setUndirectEdges(int _a, int _b) {
		adj[_a].push_back(_b);
		adj[_b].push_back(_a);
	}
	void setDirectEdges(int _a, int _b) {
		adj[_a].push_back(_b); // 방향성이 있으므로 하나만 삽입
	}

	void BFS(int _start) {
		queue<int> Q;
		Q.push(_start);
		visited[_start] = true;
		while (!Q.empty()) {
			_start = Q.front();
			Q.pop();
			cout << _start << ' ';
			list<int>::iterator iter; //이터레이터
			for (iter = adj[_start].begin(); iter != adj[_start].end(); ++iter) {
				if (!visited[*iter]) {
					visited[*iter] = true;
					Q.push(*iter);
				}
			}
		}
	}

	void DFS(int _start) {
		stack<int> S;
		S.push(_start);
		visited[_start] = true;
		while (!S.empty()) {
			_start = S.top();
			S.pop();	
			cout << _start << ' ';
			list<int>::iterator iter; //이터레이터
			for (iter = adj[_start].begin(); iter != adj[_start].end(); ++iter) {
				if (!visited[*iter]) {
					visited[*iter] = true;
					S.push(*iter); 
				}
			}
		}
	}

	void initializing_visited() {
		for (int i = 0; i < vertices; i++) {
			visited[i] = false;
		}
	}
};

int main() {

	Graph MyGraph(10);
	MyGraph.setUndirectEdges(1, 2);
	MyGraph.setUndirectEdges(1, 3);
	MyGraph.setUndirectEdges(2, 5);
	MyGraph.setUndirectEdges(2, 6);
	MyGraph.setUndirectEdges(3, 4);
	MyGraph.setUndirectEdges(4, 6);
	MyGraph.setUndirectEdges(4, 7);
	MyGraph.setUndirectEdges(4, 9);
	MyGraph.setUndirectEdges(8, 9);

	cout << "BFS 결과: ";
	MyGraph.BFS(1);
	MyGraph.initializing_visited();
	cout << '\n';
	cout << "DFS 결과: ";
	MyGraph.DFS(1);

	return 0;
}

 

 

+) 코드에 이터레이터가 사용되었다.

 

이터레이터란?

포인터와 상당히 비슷하며, 컨테이너에 저장되어 있는 원소들을 참조할 때 사용된다.

(stack, queue에는 iterator가 없다)

 

사용

vector<int> v;

vector<int>::iterator iter;

for (iter = v.begin(); iter != v.end(); ++iter) {

    cout << *iter << " "; // 이터레이터가 참조하고 있는 것을 출력

}

 

 

 

5. BFS 관련 문제 풀이

 

https://www.acmicpc.net/problem/1260