안녕하세요. 자료 구조 내용 정리 – DFS, BFS 관련 포스팅입니다.
DFS는 Depth First Search의 줄임말로 깊이 우선 탐색을 뜻합니다.
그리고 BFS는 Breath First Search의 줄임말로 너비 우선 탐색을 뜻합니다.
이 내용들을 간단하게 정리하여 공유드리니 편하게 읽어주시면 될 것 같습니다.

이 게시물과 관련하여 영상으로도 제작을 해봤는데요.
한번 시청해주시면 감사하겠습니다.

본문의 사이즈가 있어서 좀 어그러져 보이는데, 이건 링크타고 유튜브에서 직접 시청하시면 됩니다.
여기서 사용하는 PPT를 활용하여 설명을 드리려고 합니다.

네.
메인페이지라 이건 그냥 넘어가겠습니다..

DFS

DFS에 관한 정의내용입니다.
DFS는 그래프 탐색의 한 종류입니다.
깊이 우선 탐색이라고 부르는데요.
루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방식으로 탐색을 하는 방식입니다.
이 자료구조는 Stack을 활용하여 구현을 합니다.

스택과 관련된 내용은 아래 링크 및 영상을 참고해주시면 감사하겠습니다.
You Tube :

DFS 장점과 단점

DFS의 장점과 단점은 아래와 같습니다.

• 장점
  • 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적음
  • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음

• 단점
  • 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있음
  • 얻어진 해가 최단 경로가 된다는 보장이 없음

DFS 흐름

위 그림은 한개의 그래프를 그려보았습니다.
동그라미로 표시된 것을 노드 또는 정점(Vertex)라고 정의하고, 각 노드를 연결한 선은 간선(Edge)라고 부릅니다.

DFS에서의 흐름을 정리해둔건데, 모바일에서는 잘 보이지 않을 수 있겠네요.
1번 정점에서 시작을 한다고 예를 든다면, DFS는 아래와 같은 흐름을 가집니다.

1 → 2 → 4 → 8 → 5 → (8) → 6 → 3 → 7

여기에서 중간에 괄호가 쳐져있는 8이 있는데요.
이건 실제로 방문한 것은 아니지만, 제가 위에 정의를 말씀드린 부분에서 보시다시피 ‘다시 되돌아와’ 탐색을 시작한다는 것을 보여드리기 위해 표현해드린 부분입니다.
이해를 위한 부분이니 이 점 참고해주시면 감사하겠습니다.

DFS 구현 방법 – 인접행렬

DFS를 구현하는 방법은 2가지가 존재합니다.
그 중 한가지는 인접행렬인데요. 이 부분을 먼저 설명드리도록 하겠습니다.
인접 행렬(Adjacency Matrix)는 행렬로 정점들 사이의 관계를 표현하는 것입니다.
간선 방향의 존재 유무에 따라 표현하는 방법에 차이가 있습니다.

DFS 인접 행렬 코드

위 내용은 중요한 부분의 코드를 작성해서 공유드린 부분인데, 이 코드는 제가 강의용으로 공개한 GitHub Repository에서 확인하실 수 있습니다.

Github Repository : Link

주요 변수를 설명드리면 아래와 같습니다.

edge : 간선의 수
vertex : 정점의 수
map : 정점 간의 연결 정보를 담는 객체
visit : 정점을 방문했는지 체크하기 위해 생성한 객체

DFS 구현방법 – 인접 리스트

그리고 두번째 구현 방법은 ‘인접 리스트’로 구현하는 것입니다.
인접 리스트 방식은 List 방식으로 각 정점이 연결된 노드들의 정보를 저장하는 방식입니다.
간선 방향의 존재 유무에 따라 출발지 도착지를 고려하여 리스트에 정보를 저장합니다.

DFS 인접 리스트 구현 코드

위 내용은 인접 리스트에 관한 코드를 캡쳐해둔 부분인데요.
이것 또한 위에 걸어둔 링크를 참고하여 보시면 되겠습니다.

YouTube : Link
ThinkGround Post : Not yet published

BFS

이제 BFS 입니다.
BFS도 그래프 탐색의 한 종류인데, 너비 우선 탐색이라고 부릅니다.
루트 노드나 임의의 노드에서 시작하여 인접한 노드를 먼저 모두 확인한 후 다음 Depth를 탐색합니다.
BFS는 Queue를 사용하여 구현합니다.

BFS 특징

BFS의 특징은 아래와 같습니다.
BFS는 시작 정점부터 거리가 가까운 정점의 순서로 탐색합니다.
그리고 재귀적으로는 동작하지 못하는 특징이 있습니다.
그리고 Queue를 활용하여 구현하기 때문에 FIFO (First In First Out) 을 따라줍니다.

BFS 흐름

BFS의 흐름을 이해하신다면 개념은 다 이해했다고 보실 수 있습니다.
1번 노드에서 시작한다는 가정하에 아래와 같은 순서로 진행됩니다.

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8

BFS 구현코드

위 코드는 아래 레포지토리 링크에서 확인하실 수 있습니다.

GitHub Repository : Link

Updated by 21.01.30 자료 구조 내용 정리 – DFS, BFS
Site : @ThinkGround
Instagram : @thinkground_official
Facebook : @ThinkGround
Twitter : @ThinkG_Flature
YouTube : @Link