알고리즘26 Kruskal 알고리즘 (MST) 크루스칼 알고리즘은 간선을 하나씩 선택해서 MST를 찾는 알고리즘이다. 이때, 모든 간선을 가중치에 따라서 오름차순으로 정렬을 하고, 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. 물론 사이클이 존재하면 안되기 때문에 사이클이 될 경우는 건너뛰고 다음으로 가중치가 낮은 간선을 선택한다.\ 이를 간선이 n-1개 선택될 때까지 반복하게 된다. 위와 같이 정렬한 뒤 정점에 대한 간선을 가중치에 따라 선택한 경우다. 이를 코드로 작성해보자. 우선 2차원 배열을 만드는데, 정점의 개수 만큼의 행을 만들고, 3개의 열을 만든다. 0번째 열은 시작 정점 1번째 열은 끝 정점 2번째 열은 가중치를 저장할 것이다. int v; int e; int edges[][]= new int [e][3]; //0 시작 .. 2023. 3. 29. 최소 비용 신장 트리(Minimum Spanning Tree, MST) 신장 트리란 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 일컫는다. 그렇다면 최소 신장 트리는 무엇일까? 최소 신장 트리는 위에서 구한 신장 트리 중에서, 사용된 간선들의 가중치의 합이 최소인 트리를 말한다. 즉 모든 정점을 방문하는 간선의 부분 집합은 무수히 많지만, 그 중에서 간선이 가지는 가중치의 합이 가장 작은 트리를 말하는 것이다. 최소 신장 트리의 특징으로는 - 무방향성이고 가중치를 가지는 그래프 - 그래프에서 간선이 가지는 가중치의 합이 최소 - N개의 정점을 가지는 그래프에서 반드시 (N-1)개의 간선을 사용 - 사이클 미포함 등을 들 수 있다. 최소 신장 트리를 사용하는 이유는 각 정점을 잇는 작업에서 비용을 최소화해야 할 때 사용할 수 있기 때문에 도로망, 통신망, 유통망.. 2023. 3. 29. 서로소 집합(Disjoint Set) 연산 지난 번에 서로소 집합, 즉 상호 배타 집합에 대해 알아 보았다. 이번에는 상호 배타 집합 연산에서 Rank를 이용한 방법과 Path Compression을 이용한 방법을 알아보자. 우선 Rank를 이용하는 것은 간단하다. 각 노드는 자신을 루트로 하는 SubTree의 높이를 Rank라는 이름으로 저장한다. 이를 이용해 두 집합을 합칠 때 Rank가 낮은 집합을 Rank가 높은 집합에 붙이는 것이다. 위와 같이 랭크가 2인 루트 노드에 랭크가 1인 루트 노드를 붙이면 랭크의 증가 없이 추가할 수 있다. 그렇다면 랭크가 같은 경우는 어떨까? 랭크가 같은 경우 일단 이어 붙인 후 랭크를 증가시켜줘야 한다. 다음은 랭크를 통한 Union 연산이다. Union(x,y){ cal(Find-Set(x),Find-S.. 2023. 3. 29. 서로소 집합, 상호 배타 집합(Disjoint-Sets) 서로소 또는 상호 배타 집합들은 서로 중복으로 퐇마된 원소가 없는 집합들을 말한다. 즉, 서로소 집합들은 서로간의 교집합이 없는 것이다. 서로소 집합은 집합에 속한 하나의 특정 멤버를 통해서 각 집합들을 구분할 수 있다. 이를 대표자(Representative)라고 한다. 상호 배타 집합, 즉 서로소 집합을 표현하는 방법으로는 연결 리스트, 트리 등이 있다. 또 이와 관련된 연산은 Make-Set(x) - 대표자가 x인 집합을 만드는 연산 Find-Set(x) - 대표자가 x인 요소를 찾는 연산 Union(x,y) - 대표자가 각각 x, y인 집합을 합하는 연산 등과 같이 들 수 있다. 위에서 언급한 것처럼 서로소 집합의 표현 방법으로는 연결 리스트, 트리 등으로 할 수 있다고 했는데, 연결리스트의 경우.. 2023. 3. 29. 이전 1 2 3 4 5 6 7 다음
