가중치 그래프(MCST)
간선에 가중치가 부여된 그래프를 가중치 그래프라고 한다.
최소 비용 신장 트리
신장 트리 비용은 신장 트리를 구성하는 간선들의 가중치를 합한 것을 말하고, 이 비용이 최소가 되는 신장 트리를 "최소 비용 신장 트리"라고 한다.
최소 비용 신장 트리 알고리즘에는 대표적으로 Kruskal Algorithm이 있다.
Kruskal Algorithm (크루스칼 알고리즘)
방법
- 한 번에 하나나의 간선을 선택하되 비용이 가장 작은 간선을 택하여 최소 비용 신장 트리 T에 추가한다.
(n개의 정점을 가진 그래프 G의 간선의 집합 E(G)로부터 n-1개의 간선을 선정하는 것임) - 비용이 가장 작은 간선을 선정하되, 이미 T에 포함된 간선들과 사이클이 만들어지는 것은 제외시킨다.
- 비용이 같은 간선들은 임의의 순서로 하나씩 추가한다.
구현
- 최소 비용 간선 선택
- 그래프 G의 간선들을 가중치에 따라 오름차순으로 정렬한 간선의 순차 리스트 유지.
- 사이클 검사
- T에 추가로 포함될 정점들을 연결 요소별로 정점 그룹을 만들어 유지.
- 간선(i, j)가 T에 포함되기 위해서는 사이클이 형성되지 않아야 한다. 즉, 정점 i와 j가 각각 상이한 정점 그룹에 속해 있어야 한다.
코드 구현
<메소드 클래스>
public class UndirectWeightedGraph {
private String V; // 그래프의 Node 집합
private Edge E[]; // 그래프의 Edge 집합
// 파일로부터 값을 읽어들여서 Edge 데이타를 초기화해주는 메소드
public void readFile() {
V = "";
E = new Edge[9];
E[0] = new Edge('0', 5, '1');
E[1] = new Edge('0', 4, '2');
E[2] = new Edge('1', 2, '2');
E[3] = new Edge('1', 7, '3');
E[4] = new Edge('2', 6, '3');
E[5] = new Edge('2', 11, '4');
E[6] = new Edge('3', 3, '4');
E[7] = new Edge('3', 8, '5');
E[8] = new Edge('4', 8, '5');
addNode();
}
private void addNode()
{
for(int i=0; i<E.length; i++)
addNode(E[i].VERTEX_1, E[i].VERTEX_2);
}
//노드에 대한 정보를 추가시킨다.
private void addNode(char v1, char v2){
addNode(v1);
addNode(v2);
}
//노드에 대한 정보를 추가시키는 메인 메소드
private void addNode(char node){
if ( V.indexOf(node) == -1 )
//문자열 V에 매개변수로 받은 node가 있는 지 확인하고 없다면 v에 node를 추가
V += node;
}
// 문자열 V에 정점들을 저장한다.
// Kruskal 알고리즘에 의한 연산처리 메소드
public void kruskal() {
System.out.println(":::입력된 Edge 집합::: (스택을 이용해서 역순임)");
for (int i = 0 ; i < E.length ; i++) {
System.out.println(E[i]);
}
Sort();
System.out.println("\n:::정렬된 Edge 집합::: ");
for (int i = 0 ; i < E.length ; i++) {
System.out.println(E[i]);
}
System.out.println("\n:::최소 비용 Edge 집합::: ");
UNION_FIND uf = new UNION_FIND( V.toCharArray() ); // 연산을 위한 집합생성
// Edge 의 수만큼 루프반복
for (int i = 0, k = 1 ; i < E.length ; i++) {
// Find 연산자를 이용해서 사이클인지를 확인함 (find 내부에 union 연산포함)
if ( uf.find(E[i].VERTEX_1, E[i].VERTEX_2) ) {
visit(i); // 찾아낸 최단경로에 대한 처리
// 결과트리의 Edge 의 수가 V-1 이되면 종료.
if ( k == V.length()-1 ) break;
else k++;
}
}
}
// 최소비용 에지를 방문했을때에 대한 처리
public void visit(int i) {
System.out.println(E[i]);
}
public void Sort()
{
for(int i=0;i<E.length-1;i++)
for(int j=i+1;j<E.length;j++)
if(E[i].WEIGHT > E[j].WEIGHT)
{
Edge temp;
temp = E[i];
E[i] = E[j];
E[j] = temp;
}
}
}
<Edge 클래스>
public class Edge {
char VERTEX_1; // edge 의 정점 한쪽 점
char VERTEX_2; // edge 의 정점 다른 한쪽의 점
int WEIGHT; // edge 의 가중치
// Edge 에 값을 입력하기 위한 생성자
public Edge(char v1, int w, char v2) {
VERTEX_1 = v1;
VERTEX_2 = v2;
WEIGHT = w;
}
public String toString() {
return VERTEX_1 + "-" + VERTEX_2 + " 가중치:" + WEIGHT;
}
}
<메인 클래스>
import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
public class KruskalTest {
public static void main(String args[]) {
UndirectWeightedGraph graph = new UndirectWeightedGraph();
graph.readFile();
graph.kruskal();
}
}
Union / Find (집합의 처리)
- 트리에서 각 노드의 숫자는 배열에서 i를 나타낸다.
- 배열에서 트리의 루트는 -1이고, 각 노드의 PARENT는 부모를 저장한다.
- VALUE에는 정점을 저장, HEIGHT에는 높이를 저장한다.
배열 초기의 모습을 그대로 저장한 모습이다.
S1, S2, S3의 상태에 맞게 배열에 저장한 모습이다.
0, 4, 2는 root이므로 PARENT 값이 -1로 저장되어 있다.
S1에 S2를 합친 뒤 배열에 저장한 모습이다.
루트였던 정점 4가 S1에 자식으로 합쳐져 PARENT 값이 0으로 바뀌었다.
HEIGHT가 2였던 S1에 S2가 합쳐져 정점 0의 HEIGHT가 3으로 바뀌었다.
이 그림은 반대로 S2에 S1이 합쳐진 모습이다.
루트였던 정점 0이 S1에 자식으로 합쳐져 PARENT 값이 4로 바뀌었다.
HEIGHT가 2였던 S2에 S1이 합쳐져 정점 4의 HEIGHT 값이 3으로 바뀌었다.
가중치 규칙을 사용한 Union 연산이다.
내가 사용한 규칙은 Union 진행 시 높이가 높은 그래프에 높이가 작은 그래프를 자식으로 만드는 방법이다.
두 트리를 합칠 때 높이가 더 큰 트리가 루트가 되고,
두 트리의 높이가 같다면 루트 하나를 기준으로 합치고, 기준이 되었던 루트의 높이를 +1 증가시킨다.
위 그림은 S1에 S2가 자식으로 합쳐졌기 때문에 S1의 높이가 +1 씩 증가한 것이다.
Union-Find에서 HEIGHT는 실제 트리의 물리적인 "노드 개수" 나 "자식 수"가 아니라, 트리의 깊이를 근사적으로 나타낸 값이다.
자식이 없다고 해서 높이가 1이 아니고 Union 연산을 수행할 때 트리 병합의 기준이 되기 위해 사용된다.
find() 연산, root를 찾는 함수
예를 들어 원소 9의 루트를 찾을 때 배열 값을 보고 찾아가며 최종적으로 PARENT의 값이 -1 이면 루트를 찾은 것이다.
원소 9의 PARNET 값은 4이다.
그럼 원소 4를 살펴본다.
원소 4의 PARENT 값은 0이다.
그럼 원소 0을 살펴본다.
원소 0의 PARENT 값은 -1이다.
결과적으로 원소 9의 루트는 0이 된다.
<Union_Find 클래스>
public class UNION_FIND {
private char[] VALUE; // 집합의 값
private int[] PARENT; // 집합의 부모의 값
private int[] HEIGHT; // 집합의 높이값
// 집합을 초기화시키기 위한 생성자
public UNION_FIND(char[] v) {
VALUE = new char[v.length];
PARENT = new int[VALUE.length];
HEIGHT = new int[VALUE.length];
for (int i = 0 ; i < VALUE.length ; i++) {
VALUE[i] = v[i];
PARENT[i] = -1;
HEIGHT[i] = 1;
}
}
// 집합의 Union 연산 메소드 (v와 u중에서 큰쪽에 작은 쪽의 트리를 합친다.)
public void union(int vNum, int uNum) {
// 두 트리의 높이가 똑같다면
if ( HEIGHT[vNum] == HEIGHT[uNum] )
HEIGHT[vNum]++; // vNum 트리의 높이를 1 증가
// 두 트리의 높이가 다르다면 큰쪽에 작은쪽을 붙인다.
if ( HEIGHT[uNum] > HEIGHT[vNum] ) {
int temp = uNum;
uNum = vNum;
vNum = temp;
}
// 높이가 더 큰 쪽(vNum)의 자식으로 작은쪽(uNum)을 붙임
PARENT[uNum] = vNum;
}
// 집합의 Find 연산 메소드 (v 가 속한 집합과 u 가 속한 집합이 다른가를 검색, 같으면 false 다르면 true)
// 같은 집합에 속하지 않는다면 Union 연산을 하도록 한다. 즉, true 조건에서만 Union()을 하게 된다.
public boolean find(char v, char u) {
int vNum = -1, uNum = -1;
// System.out.println("v:" + v + " u:" +u);
// v와 u의 index값인 vNum 과 uNum 을 찾는다.
for (int i = 0 ; i < VALUE.length ; i++) {
if ( VALUE[i] == v ) vNum = i;
else if ( VALUE[i] == u ) uNum = i;
if ( vNum != -1 && uNum != -1 ) break;
}
// v를 root를 찾는다
while (PARENT[vNum] > -1)
vNum = PARENT[vNum];
// u의 root 를 찾는다.
while (PARENT[uNum] > -1)
uNum = PARENT[uNum];
// 두개가 같은 집합이 아니면 즉 사이클이 아니라면 union 을 해준다.
if ( vNum != uNum ) {
union(vNum, uNum);
// System.out.println("vNum: " + vNum + " uNum: " + uNum);
return true;
}
return false;
}
public String toString() {
String str = "";
for (int i = 0 ; i < VALUE.length ;i++) {
String k = "Root";
if ( PARENT[i] != -1 )
k = String.valueOf(VALUE[PARENT[i]]);
str += VALUE[i] + " " + k + " " + HEIGHT[i] +"\n";
}
return str;
}
}'CS > 자료구조, 알고리즘' 카테고리의 다른 글
| 트리와 이진 트리 (0) | 2025.10.20 |
|---|