Closed L-j-h-c closed 2 years ago
그래프에서 모든 정점을 방문해야 할 때가 자주 있는데, 이를 그래프 탐색이라고 한다. 그래프 탐색의 대표적인 방법으로 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)가 있는데, 우선 BFS에 대해서 알아보자.
우선 직관을 돕기 위해 BFS를 설명한 그림부터 살펴보자.
Root Node인 0부터 출발하여 Root로부터 인접한 Node들부터 탐색하고, 점점 탐색 범위를 넓혀나가고 있다. 이런 점에서 이러한 그래프 탐색 방식을 너비 우선 탐색이라고 부른다.
구현 BFS를 구현하기 위해서는 Queue를 이용할 수 있다. 대상이 무방향 그래프라고 가정할 때, 기본 원리는 정점을 처음으로 방문할 때 큐에 삽입하고, 큐에정점을 하나씩 Dequeue 하면서 그에 인접한 정점들을 큐로 삽입하는 식으로 진행한다.
이는 큐가 빌 때까지 지속하며, 새로운 원소를 큐에 삽입할 때에는 이미 방문한 정점이 아닌 경우에만 삽입해 준다.
활용 세상의 모든 사람이 지닌 친분관계를 그래프로 나타냈을 때, 특정인 A와 B 사이 간선의 최단 경로를 구할 때 사용해줄 수 있다.
https://velog.io/@vagabondms/DFS-vs-BFS
L-j-h-c
commented
2 years ago L-j-h-c
commented
2 years ago
BFS(너비 우선 탐색), Breadth-First Search
그래프에서 모든 정점을 방문해야 할 때가 자주 있는데, 이를 그래프 탐색이라고 한다. 그래프 탐색의 대표적인 방법으로 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)가 있는데, 우선 BFS에 대해서 알아보자.
우선 직관을 돕기 위해 BFS를 설명한 그림부터 살펴보자.
Root Node인 0부터 출발하여 Root로부터 인접한 Node들부터 탐색하고, 점점 탐색 범위를 넓혀나가고 있다. 이런 점에서 이러한 그래프 탐색 방식을 너비 우선 탐색이라고 부른다.
구현 BFS를 구현하기 위해서는 Queue를 이용할 수 있다. 대상이 무방향 그래프라고 가정할 때, 기본 원리는 정점을 처음으로 방문할 때 큐에 삽입하고, 큐에정점을 하나씩 Dequeue 하면서 그에 인접한 정점들을 큐로 삽입하는 식으로 진행한다.
이는 큐가 빌 때까지 지속하며, 새로운 원소를 큐에 삽입할 때에는 이미 방문한 정점이 아닌 경우에만 삽입해 준다.
활용 세상의 모든 사람이 지닌 친분관계를 그래프로 나타냈을 때, 특정인 A와 B 사이 간선의 최단 경로를 구할 때 사용해줄 수 있다.