방문함
스택에 있음
확인한 간선

  • 현재
  • 스택에 있음
  • 완료
  • 경로
노드 클릭으로 설정

깊이 우선 탐색 더 알아보기

깊이 우선 탐색 (DFS)

깊이 우선 탐색은 한 손을 벽에 대고 미로를 걷는 사람처럼 그래프를 탐색합니다. 한 경로를 갈 수 있는 데까지 따라가고, 새로 갈 곳이 없을 때만 되돌아갑니다. 이를 스택으로 해냅니다. 노드를 클릭해 거기서 시작하고, 원하면 목표를 고른 뒤 탐색을 한 단계씩 진행하며 스택이 늘었다 줄었다 하는 모습, 각 노드가 받는 방문 번호, 사이클을 닫는 간선을 확인하세요. 재생을 눌러 탐색을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 노드를 클릭하면 시작 노드가 됩니다. 클릭을 목표로 바꾸고 다른 노드를 클릭하면 그 노드까지의 경로를 찾습니다. 각 노드의 숫자는 방문한 순서이고, 그래프 아래의 줄은 시작 노드부터 맨 위 노드까지의 스택입니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.

작동 원리

  1. 노드를 클릭해 시작 노드로 정합니다. 경로를 찾으려면 클릭을 목표로 바꾸고 다른 노드를 클릭하세요.
  2. 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 탐색의 원하는 곳으로 이동합니다.
  3. 그래프 아래의 스택과 각 노드의 방문 번호를 지켜보세요. 새 그래프로 다른 그래프를 시도할 수 있습니다.

깊이 우선 탐색의 작동 방식

시작 노드를 스택에 넣습니다. 그다음 반복합니다. 스택 맨 위 노드의 다음 이웃을 봅니다. 아직 보지 않은 이웃은 다음 방문 번호를 받고, 어느 노드에서 도달했는지 기억한 뒤 스택 맨 위에 올라가므로, 탐색은 거기서 이어집니다. 맨 위 노드에 확인할 이웃이 남지 않으면 그 노드는 완료되어 스택에서 빠지고, 탐색은 그 아래 노드로 되돌아갑니다. 스택이 비면 도달할 수 있는 모든 노드를 방문한 것입니다.

스택이 알려 주는 것

탐색은 항상 가장 새로운 노드에서 이어 가므로, 스택은 항상 시작 노드에서 지금 보고 있는 노드까지의 경로입니다. 목표에 도달하면 스택이 그곳까지의 경로가 되지만, 대개 최단 경로는 아닙니다. 최단 경로는 너비 우선 탐색이 찾습니다. 방향이 없는 그래프에서, 방금 온 노드가 아니면서 아직 스택에 있는 노드로 가는 간선은 사이클을 닫습니다. 기억한 노드들은 트리, 즉 깊이 우선 트리를 이루고, 노드가 완료되는 순서는 위상 정렬의 핵심입니다.

자주 묻는 질문

깊이 우선 탐색이란 무엇인가요?

시작 노드에서 그래프를 탐색하는 방법으로, 한 경로를 최대한 깊이 따라가다가 새로 갈 곳이 없을 때만 되돌아가 다른 가지를 시도합니다. 돌아갈 길을 기억하려고 스택이나 재귀를 사용합니다.

깊이 우선 탐색은 최단 경로를 찾나요?

아니요. 목표로 가는 경로가 있으면 찾지만, 그 경로는 필요보다 훨씬 길 수 있습니다. DFS는 처음 시도한 가지를 끝까지 따라가기 때문입니다. 간선 수가 가장 적은 경로는 너비 우선 탐색으로, 간선에 길이가 있으면 다익스트라 알고리즘으로 찾으세요.

DFS와 BFS의 차이는 무엇인가요?

깊이 우선 탐색은 스택을 사용하며 한 경로를 깊이 들어간 뒤 되돌아옵니다. 너비 우선 탐색은 큐를 사용하며 고리 모양으로 고르게 퍼져 나갑니다. 둘 다 도달할 수 있는 모든 노드를 노드 수와 간선 수의 합에 비례하는 시간에 방문합니다. BFS는 최단 경로를 찾고, DFS는 사이클, 미로, 위상 정렬에 자연스럽게 쓰입니다.

DFS는 어떻게 사이클을 찾나요?

방향이 없는 그래프에서 탐색이 아직 스택에 있는 노드로 가는 간선을 만나고, 그 노드가 방금 온 노드가 아니면 그 간선이 고리를 닫습니다. 앱에서는 그럴 때 상태 표시줄에 알려 줍니다.

내 그래프가 어딘가로 전송되나요?

아니요. 그래프는 브라우저 안에서 만들어지고 탐색되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동