[Graph] 순회(Traversal algorithms)

그래프 순회(Traversal)

그래프는 순회를 위해 가장 낮은 지점인 시작점 부터 인접한 정점으로 이어 나가는 구조입니다.
스택, 리스트와 같이 선형 구조가 존재하지 않아 하나의 정점을 시작점으로 사용합니다.

그래프 순회 이용

그래프는 P2P 네트워크, 최단 경로, GPS 시스템, 가비지 수집 프로그램에 사용되기도 합니다.

그래프 순회 유형

1. 너비 우선 검색 (BFS)
2. 깊이 우선 검색 (DFS)

 

BFS

동일한 높이에 있는 노드들을 모두 통과하면 다음 높이로 이동하며 순회합니다.

 

DFS

가장 깊은 높이까지 도달하도록 이동합니다.
다시 시작점으로 돌아와 인접한 다른 노드를 선택하고 가장 깊은 높이까지 도달하도록 이동합니다.
이 과정을 반복하여 모든 노드를 방문할 때까지 실행됩니다.

 

BFS 시간복잡도

인접 리스트 : O(V+E)
인접 행렬 : O(V^2)

 

DFS 시간복잡도

인접 리스트 : O(V+E)
인접 행렬 : O(V^2)