그래프 탐색

그래프의 탐색 이란?

• 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘
• 깊이 우선 탐색과 너비우선 탐색이 있다.

---

깊이 우선 탐색

• 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법
• 현재 정점과 인접한 간선들을 하나씩 검사하다가 아직 검사하지 않은 간선이 있다면 방문 
• 더이상 갈곳없는 막힌 정점에 도달하면 되돌아감

그래프의 깊이우선 탐색 순서

---

깊이 우선 탐색의 시간 복잡도

인접리스트 이용

for문에 의해 V번 호출

각 정점에서 dfs()가 호출(E번)

따라서 시간복잡도는 O(V+E)

 

인접행렬 사용

인접행렬은 2차원 배열을 모두 탐색(V*V)

따라서 O(V^2)