그래프(Graph)와 BFS, DFS

그래프(Graph)

그래프란 여러 객체들과 그 객체들 간의 연결된 관계를 표현하는 방법 입니다.

친숙한 예제로 지하철 노선도를 생각해보시면 됩니다. 여러 지하철역들과 그 역들 간의 연결된 관계를 표시 해줍니다.

그래프에서 각 객체ㅁ들을 정점(vertex) 혹은 노드(node)라고 많이 부르고, 이들을 연결하는 선들을 간선(edge-엣지) 라고 부릅니다.

이미지 출처 : https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

BFS(Breadth First Search)

그래프의 모든 노드들을 한번 씩 탐색하기 위한 방법 중에 하나입니다. 말그대로 너비(Breadth)를 우선(First)으로 탐색(Search)하는 방법입니다. 시작점이 되는 노드를 기준으로 탐색해야 할 노드들이 있다면 (= 연결된 노드들이 있다면) 그 노드들을 우선적으로 모두 방문합니다. 더이상 방문해야할 노드가 없다면 다시 인접한 노드들의 탐색해야 할 노드가 있는지 확인하고 방문합니다. 이런 식으로 탐색햐야 할 노드가 없을 때까지 진행합니다.

DFS(Depth First Search)

그래프의 모든 노드들을 한번 씩 탐색하기 위한 방법 중에 하나입니다. 말그대로 깊이(Depth)를 우선(First)으로 탐색(Search)하는 방법입니다. 시작점이 되는 노드를 기준으로 탐색해야 할 노드들이 있다면 (= 연결된 노드들이 있다면) 그 노드중에 하나를 방문하고, 다시 방문한 노드를 기준으로 탐색해야 할 노드들이 있다면 그 노드들을 우선적으로 방문합니다. 이런 식으로 탐색해야 할 노드가 없을 때까지 진행합니다.

BFS vs DFS

둘의 차이점을 그래프의 한 종류인 트리로 보면 쉽습니다. (그렇다고 BFS, DFS가 트리구조에만 국한된 개념은 아닙니다.)

이미지 출처 : http://mishadoff.com/blog/dfs-on-binary-tree-array/

더 공부해 볼만한 키워드

방향 그래프 vs 무방향 그래프 / 사이클 / 가중치 그래프