그래프 탐색(DFS·BFS) 순서 계산기

다음에 갈 곳을 어디에 담아 두느냐가 다릅니다. DFS는 스택이라 가장 나중에 담은 곳으로 가 한 갈래를 끝까지 파고들고, BFS는 큐라 가장 먼저 담은 곳으로 가 가까운 곳부터 훑습니다. 그래서 BFS의 방문 순서는 시작점에서 가까운 순이고, 간선에 가중치가 없을 때는 그 거리가 곧 최단거리입니다.

한 정점에 이웃이 여럿일 때 어느 쪽을 먼저 보느냐에 따라 순서가 통째로 달라지기 때문입니다. 규약을 정하지 않으면 답이 여러 개가 됩니다. 이 계산기는 언제나 이름이 앞서는 이웃부터 보며(숫자는 숫자 크기대로), 결과 표의 «이웃» 열이 실제로 보는 순서입니다.

탐색 도중 «아직 나오지 않은 조상»으로 가는 간선(역방향 간선)이 하나라도 있으면 사이클이 있습니다. 돌아오는 길이 있다는 뜻이기 때문입니다. 무방향 그래프에서는 방금 온 길을 되돌아보는 것은 세지 않아야 하며, 이 계산기는 그것을 걸러 냅니다.

간선을 종류별로 가르는 데 씁니다. 아직 안 가 본 곳으로 가면 트리 간선, 아직 안 나온 조상으로 가면 역방향, 이미 끝난 자손으로 가면 순방향, 이미 끝난 다른 가지로 가면 교차 간선입니다. 순방향과 교차 간선은 방향 그래프에만 나옵니다.

한 정점에서 탐색을 끝냈는데 아직 안 가 본 정점이 남으면, 남은 곳에서 다시 시작하기를 되풀이합니다. 그 횟수가 연결 요소의 개수입니다. 방향 그래프에서는 «시작점에서 갈 수 있는 곳»과 «연결되어 있음»이 다른 이야기라, 이 계산기는 방향을 무시하고 센 값을 보여 줍니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.