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