Data Structure (2) 썸네일형 리스트형 Sollin's algorithm(Borůvka's algorithm) 최소 비용 신장 트리 구하는 알고리즘 중 가장 자료가 없는 Sollin's algorithm 혹은 (Borůvka's algorithm)에 대해서 정리를 해보겠다. 최소 비용 신장 트리는 신장트리를 만드는데, 간선의 가중치 합이 최소가 되도록하는 알고리즘이다. 다음과 같은 그래프가 있다고 하자. 각각의 정점에 연결된 간선 중 가중치가 가장 작은 간선만을 선택한다. 0->6, 1->7, 2->7, 3->12, 4->12, 5->6, 6-> 10 이제 각각의 트리들이 만들어졌는데, 가장 작은 가중치를 갖는 간선을 이용하여 이어준다. (이것에 대한 구체적인 알고리즘은 없는 것으로 보인다.) 다음 경로가 바로 Sollin's algorithm의 결과물, 최소 비용 신장 트리이다. 이중 결합 요소(Biconnected Components) [2023-1R 고려대학교 최수경 교수님 Cose 213 자료구조 수강 중 내용 정리하는 글입니다.] 이중 결합 그래프(Biconnected Graph) - 단절점(articulation point)가 없는 연결 그래프를 의미한다. 단절점(articulation point) - 무방향 연결 그래프에서 어떠한 정점을 제거했을 때 그래프의 연결이 끊어지면 그 정점을 단절점이라고 한다. Biconnected Components(이중 결합 요소) - 단절점을 기준으로 연결된 그래프들로 분리해주면 하나하나가 Biconnected Components이다. Biconnected Components 구하기 알고리즘 -Depth first spanning tree를 이용하여 구현함. 3에서 출발을 했다면 아래 순서대로 .. 이전 1 다음
