: Graph 순회 방법

DFS (Depth-First Search, 깊이우선탐색)

사진출처

깊이 내려간 후, 더이상 내려갈 곳 없으면 옆으로 이동
: Root Node나 임의의 Node에서 다음 분기(Branch)로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식

• 이미 방문한 노드를 다시 방문하면 안되므로 노드 방문여부를 체크할 배열이 필요

구현 방법

• Stack LIFO(Last In First Out;후입선출) 자료구조 또는 재귀함수로 구현

활용예시

• 모든 노드를 방문하고자 할 때 사용 ex) 미로게임에서 경로 존재유무 판별할 때

• 경로의 특징을 저장할 때

• 검색 대상 그래프가 클 경우

• 문제 예) 단절점 찾기, 단절선찾기, 사이클 찾기, 위상 정렬 등

• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

• 검색 속도는 너비 우선 탐색(BFS)에 비해서 느림

호출스택이 차지하는 최대 메모리 : 트리의 깊이

시간 복잡도

노드/정점 수(N), 엣지/간선 수(E)

• 인접 리스트 : O(N + E)

• 인접 행렬 : O(N^2)

• 깊이 우선 탐색(DFS) – 인터뷰 질문 및 연습 문제

구현하기

1. 스택으로 구현

1. Stack의 최상단 노드 확인하기
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 이 인접노드를 스택에 넣은 후 방문배열에 넣어서 방문처리한다.

방문하지 않은 인접노드 없다면 스택에서 최상단 노드를 뺀다.

2. 재귀함수로 구현

Traversal

BFS (Breadth-First Search, 너비우선탐색)

사진출처

넓게 이동 후, 더이상 이동할 수 없으면 아래로 이동
: Root Node나 임의의 Node에서 인접 노드를 먼저 탐색하는 방법.

구현 방법

• Queue FIFO(First In First Out) 자료구조로 구현
  1. 시작 노드를 큐에 삽입하고 방문처리 한다

  2. 큐에서 가장 오래된 정점을 뽑고 Dequeue
  3. 뽑은Dequeue 정점과 연결된 모든 정점중에서 방문안한 노드만 큐에 넣고 방문처리 한다
  4. 큐가 비면 반복 종료

• 재귀적으로 동작 하지 않음

• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야함
  => 검사하지 않을 경우 무한루프에 빠질 수 있음

• 호출스택이 차지하는 최대 메모리 : 트리의 너비

활용 예시

• 최단 경로, 친구 추천 등
• 그래프의 모든 정점 방문 시
• 검색 대상 규모가 작고, 검색 시작점root node에서 target node가 멀지 않을 때

시간 복잡도

정점 수(N), 간선 수(E)

• 인접 리스트 : O(N+E)
• 인접 행렬 : O(N²)

• 너비 우선 탐색(BFS) – 인터뷰 질문 및 연습 문제

참고

깊이 우선 탐색(DFS)과 너비 우선 검색(BFS)

너비 우선 탐색- 나무위키

[알고리즘] 깊이 우선 탐색(DFS)이란
[알고리즘] 너비 우선 탐색(BFS)이란

https://developer-mac.tistory.com/64