[STUDY] DFS & BFS - 그래프 탐색

dfs와 bfs를 복습할겸 정리 해본다.

 

BFS

---

Breadth-first search 란 뜻으로 그래프의 너비를 탐색하여 search 하는 알고리즘 방식이다.

우선 알고리즘을 알기 전에 노드와 간선을 알아야 한다.어려워 보이지만, 노드는 하나의 데이터를 의미하고 간선은 그런 노드와 노드를 이어주는 연견 선을 의미한다.

 

1 . 우선 방문처리할 배열 arr을 정의,초기화하고 가장 처음에 있는 노드를 큐에 넣는다.

2 . 큐에서 노드를 pop하면서 arr에 넣고, 큐에 인접노드가 없다면 이와 인접한 인접노드들을 모두 큐에 삽입한다.

3 . 위 과정을 반복한다.

 

이 과정을 수행하면 그래프에 있는 값을 bfs를 통해 한 단계씩 순서대로 파악해 나갈 수 있다.

 

따라서 위의 값은 [1,2,3,4] 가 출력된다.

 

 

DFS

---

Depth first search 라는 단어의 약자이다.

그래프에 주어졌을때, 해당 그래프의 특정 노드를 찾는 것에 특화되어있다.

 

 

1 . 우선 방문처리할 배열 arr을 정의,초기화하고 가장 처음에 있는 노드를 스택에 넣는다.

2 . 스택에서 노드를 pop하면서 arr에 넣고, 스택의 최상단 노드에 대한 인접노드가 존재하고 arr에 들어있지 않다면 스택에 담고 방문처리 한다.

3 . 위 과정을 스택에 값이 없어질때까지 반복한다.

 

위와 같은 과정을 거친다면 dfs를 통해서는 [1,2,4,3] 이라는 방문 순서가 나올 것이다.