9. 그래프이론 - 신장 트리
공부할 내용 서로소 집합 신장 트리 크루스칼 알고리즘 위상 정렬 (해당 주제는 앞에서 정리했기 때문에 따로 정리하지 않아도 된다.) 공부 방법 기타 그래프 이론 - 동빈나 영상 시청 및 정리 이것이 코딩테스트다 책 참고 추천문제 풀기 (블로그에 문제 풀이를 게시하지는 않겠음) 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 원본 그래프에 존재하는 간선을 모두 활용하지 않고 일부 간선만 활용하여 모든 노드가 포함되어있는 하나의 부분 그래프를 만드는 것이다. 신장트리는 모든 노드가 다 연결되어있지만, 일부 간선을 사용하지 않아도 괜찮다는 점에서 실제 문제 상황에서도 이..