유미의 기록들

그래프를 탐색하는 방법에는 깊이우선탐색(DFS)과 너비우선탐색(BFS)가 있다 그래프를 탐색하는 것은 하나의 정점으로 시작해서 모든 정점을 한 번씩 방문하는 것, 즉 방문한 정점은 다시 방문하지 않는다 깊이 우선 탐색 (DFS, Depth First Serch) DFS는 어떤 정점부터 시작해서 다음 분기(branch)로 넘어가기 전에 각 분기마다 가능한 가장 멀리 있는 정점까지 탐색하는 알고리즘 - 모든 정점을 방문하고자 하는 경우에 많이 사용한다 - 스택 또는 재귀함수로 구현한다 너비 우선 탐색 (BFS, Breadth First Search) BFS는 어떤 정점부터 시작해서 다음 깊이의 정점로 이동하기 전에 현재 깊이의 모든 정점을 탐색하는 알고리즘 즉, 레벨 별로 탐색한다는 의미이다 - 최단 거리를..