모든 점을 잇기와 모든 길을 지나기는 어떻게 다를까?
간선을 선택하는 알고리즘도 목표는 다릅니다. 지도에 길을 새로 놓는 문제, 선후 관계를 정하는 문제, 있는 길을 모두 걷는 문제를 각각 따라가 보세요.
툴허브 편집 ·
희소 그래프를 두 방법으로 적기
정점이 많고 길이 몇 개 없는 그래프를 행렬과 리스트로 나타내 보세요. 특정 길의 존재 확인과 한 정점의 모든 이웃 찾기에서 읽게 되는 칸 수가 다릅니다.
그래프 표현 열기 →두 정점이 이미 같은 집합인지 확인하기
A와 B, B와 C를 합친 뒤 A와 C의 대표를 확인하세요. 이미 같은 집합을 다시 합치려 할 때 연결 관계는 달라지지 않습니다.
유니온-파인드 열기 →가장 싼 간선을 건너뛰는 순간 보기
간선을 비용순으로 보며 양 끝이 이미 같은 집합인지 확인하세요. 비용이 작아도 사이클을 만들면 선택에서 빠집니다.
크루스칼 MST 열기 →연결된 지점에서 뻗는 후보만 보기
처음 고른 지점에서 현재 트리 밖으로 나가는 간선을 표시하세요. 그래프 전체의 가장 싼 간선이 아직 후보에 들어오지 않은 이유를 설명해 봅니다.
프림 MST 열기 →먼저 들을 수 있는 과목부터 지우기
선수 과목이 남지 않은 과목을 하나씩 선택한다고 생각하세요. 과목이 남았는데 후보가 없으면 아직 남은 부분에 순환 의존성이 있습니다.
위상정렬 열기 →서로 돌아올 수 있는 정점 묶기
A에서 B로 갈 수 있다는 사실만으로 두 점이 같은 강한 연결 요소가 되지는 않습니다. B에서 A로 돌아오는 경로도 있는지 탐색 과정을 따라가세요.
타잔 SCC 열기 →정점 방문과 간선 사용 구분하기
한붓그리기에서는 같은 정점을 다시 지나도 되지만 같은 간선을 두 번 쓰지 않습니다. 연결된 무방향 그래프에서 홀수 차수 정점이 어디인지 먼저 세어 보세요.
오일러 경로 열기 →