본문으로 건너뛰기
툴허브

모든 점을 잇기와 모든 길을 지나기는 어떻게 다를까?

간선을 선택하는 알고리즘도 목표는 다릅니다. 지도에 길을 새로 놓는 문제, 선후 관계를 정하는 문제, 있는 길을 모두 걷는 문제를 각각 따라가 보세요.

툴허브 편집 ·

희소 그래프를 두 방법으로 적기

정점이 많고 길이 몇 개 없는 그래프를 행렬과 리스트로 나타내 보세요. 특정 길의 존재 확인과 한 정점의 모든 이웃 찾기에서 읽게 되는 칸 수가 다릅니다.

그래프 표현 열기 →

두 정점이 이미 같은 집합인지 확인하기

A와 B, B와 C를 합친 뒤 A와 C의 대표를 확인하세요. 이미 같은 집합을 다시 합치려 할 때 연결 관계는 달라지지 않습니다.

유니온-파인드 열기 →

가장 싼 간선을 건너뛰는 순간 보기

간선을 비용순으로 보며 양 끝이 이미 같은 집합인지 확인하세요. 비용이 작아도 사이클을 만들면 선택에서 빠집니다.

크루스칼 MST 열기 →

연결된 지점에서 뻗는 후보만 보기

처음 고른 지점에서 현재 트리 밖으로 나가는 간선을 표시하세요. 그래프 전체의 가장 싼 간선이 아직 후보에 들어오지 않은 이유를 설명해 봅니다.

프림 MST 열기 →

먼저 들을 수 있는 과목부터 지우기

선수 과목이 남지 않은 과목을 하나씩 선택한다고 생각하세요. 과목이 남았는데 후보가 없으면 아직 남은 부분에 순환 의존성이 있습니다.

위상정렬 열기 →

서로 돌아올 수 있는 정점 묶기

A에서 B로 갈 수 있다는 사실만으로 두 점이 같은 강한 연결 요소가 되지는 않습니다. B에서 A로 돌아오는 경로도 있는지 탐색 과정을 따라가세요.

타잔 SCC 열기 →

정점 방문과 간선 사용 구분하기

한붓그리기에서는 같은 정점을 다시 지나도 되지만 같은 간선을 두 번 쓰지 않습니다. 연결된 무방향 그래프에서 홀수 차수 정점이 어디인지 먼저 세어 보세요.

오일러 경로 열기 →