그래프 - Graph(2. DFS in undirected graphs)

2. DFS in undirected graphs

 

1. 정의 

DFS(Depth-First Search)는 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미한다. 

이 알고리즘을 사용해서 풀 수 있는 문제의 경우는 특정 도시에서 다른 도시로 갈 수 있는지 여부를 판단할 수 있고, 또 특정 지역과 지역이 연결되어 있는지 등의 여부를 판단할 수 있다. 

 

 

2. DFS의 구조(흐름도)

1

1번노드로 시작

1 -> 2 -> 4

 

1 -> 2 -> 4 -> 3 

1 -> 2 -> 4 -> 3 -> 5

 

# DFS의 경우엔 BFS와 다르게 기준점이 되는 노드에서 우선순위가 높은 노드를 먼저 순회한다. 즉, 제일 깊은 곳까지 갔다가 갈 곳이 없으면 다음으로 넘어가는 것!!!!

 

3. DFS 사용

• 스택(Stack)
• 재귀 함수(recursive)

대표적으로 DFS는 스택과 재귀를 사용해서 구현한다. 

또한 DFS는 모든 정점을 방문해야 할 때, 경로의 특징을 저장해야 하는 문제에 사용됩니다.

 

4. 시간복잡도

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

인접 행렬 : O(N²)

인접 리스트가 훨씬 효율성이 좋다.

 

 

5. DFS - 무방향 그래프

방향이 없는 그래프로 위의 그림처럼 진행되는 것으로 보면 된다. 

 

이런식으로 진행이 된다. 

 

6. DFS 정리

종류	목적	작업	시간복잡도
DFS	모든 정점 순회	모든 정점과 모든 간선(edge) 방문	O(n) + O(M)