최소 신장 트리

최소 신장트리

• 사용한 간선들의 가중치 합이 최소

• 간선 가중치를 고려하여 최소 비용의 신장 트리 선택

• 그래프의 모든 노드 포함

• 모든 노드는 서로 연결

• 사이클 X

• Kruskal 알고리즘, Prim 알고리즘으로 구현

Kruskal 알고리즘

• 가장 적은 비용으로 모든 노드 연결

• 간선 선택 기반

• 서로소 집합(Disjoint Set) / Union-Find 알고리즘 적용

• 그래프를 간선 리스트로 표현

• 순서

  1. 모든 가중치를 오름차순으로 정렬

  2. 가중치가 가장 작은 간선 선택

  3. 해당 간선이 연결하려는 노드가 서로 연결되지 않은 상태라면 2개의 노드 연결

  4. 1~3 과정을 반복

Disjoint Set 서로소 집합

• 공통 원소가 없는 두 집합

• union, find 두 가지 연산

• union

  • 두 개의 원소가 각각 포함되어 있는 집합을 하나로 합침

• find

  • 특정한 원소가 속한 집합이 어떤 집합인지 찾음

• 하나의 트리를 하나의 집합으로 볼 때, find는 트리의 루트 노드를 찾고, 그 루트 노드를 통해 특정 집합 표현

• union은 두 원소에 대해 find 연산을 수행하여 각각의 루트 노드를 찾고, 한 쪽의 루트 노드를 다른 쪽에 연결함으로써 하나의 트리로 만드는 합집합 연산 수행

static int find_parent(int x) {
	if (parent[x] != x) {
		return find_parent(parent[x]);
	}
	return x;
}

// 경로 압축 기법 적용
static int find_parent_compress(int x){
	if (parent[x] != x) {
		parent[x] = find_parent(parent[x]);
	}
	return parent[x];
}

static void union_parent(int a, int b){
	a = find_parent(a);
	b = find_parent(b);
	
	if (a < b) {
		parent[b] = a;
	} else {
		parent[a] = b;
	}
}

public static void main (String[] args) {
	Scanner sc = new Scanner(System.in);
	int V = sc.nextInt();
	int E = sc.nextInt();

	for (int i = 1; i <= V; i++) {
		parent[i] = i; // 부모 테이블 자기 자신으로 초기화
	}
	
	for (int i = 1; i <= E; i++) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		// 각 간선마다 유니온 연산
		union_parent(parent, a, b);
	}
}

프림 알고리즘

• 시작 정점을 기준으로 가장 작은 간선과 연결된 정점을 선택하여 신장 트리 확장

• Heap 이용

• 정점 선택 기반

• 그래프를 인접 리스트로 표현

• 순서

  1. 임의의 간선 선택

  2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점 선택

  3. 모든 정점이 선택될 때까지 반복

// O(N^2) 알고리즘 (배열 이용)
public static void main (String[] args) {
	Scanner sc = new Scanner(System.in);
	
	N = sc.nextInt();
	int[][] input = new int[N][N];
	int[] minEdge = new int[N];
	
	boolean[] V = new boolean[N];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			input[i][j] = sc.nextInt();
		}
		minEdge[i] = Integer.MAX_VALUE;
	}

	int minVertex, min, result = 0;
	
	minEdge[0] = 0;
	
	for (int c = 0; c < N; c++) {
		min = Integer.MAX_VALUE;
		minVertex = 0;
		// priority queue로 대체 가능

		// V와 연결된 간선 중 비용이 최소인 간선, 그 간선과 연결된 노드를 찾는다
		for (int i = 0; i < N; i++){
			if (!V[i] && min > minEdge[i]) {
				min = minEdge[i];
				minVertex = i;
			}
		}
	
		// 해당 노드를 V에 포함시킨다.
		result += min;
		V[minVertex] = true;
		
		for (int i = 0; i < N; i++) {
			// V에서 해당 노드까지 가는 최소 비용 간선 갱신
			if (!V[i] && input[minVertex][i] != 0 && minEdge[i] > input[minVertex][i]) {
				minEdge[i] = iput[minVertex][i];
			}
		}
	}
	System.out.println(result);
}

// O(E log V) 알고리즘 (Priority Queue 이용)
static class Vertex implements Comparable<Vertex> {
	int n, edge;
	public Vertex(int n, int edge) {
		super();
		this.n = n;
		this.edge = edge;
	}
	@Override
	public int compareTo(Vertex o) {
		return this.edge - o.edge;
	}
}
public static void main (String[] args) {
	Scanner sc = new Scanner(System.in);
	
	N = sc.nextInt();
	int[][] input = new int[N][N];
	int[] minEdge = new int[N];
	PrioirtyQueue<Vertex> queue = new PriorityQueue<>();
	
	boolean[] V = new boolean[N];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			input[i][j] = sc.nextInt();
		}
		minEdge[i] = Integer.MAX_VALUE;
	}

	int result = 0, nodeCount = 0;
	
	// 임의의 노드(0번 노드)를 포함시킨다
	minEdge[0] = 0;
	queue.offer(new Vertex(0, 0));
	
	while (!queue.isEmpty()) {
		Vertex minVertex = queue.poll();
		if (V[minVertex.n]) continue;
		result += minVertex.edge;
		V[minVertex.n] = true;
		if(++nodeCount == N) break;

		for (int to = 0; to < N; to++) {
			if (!V[to] && input[minVertex.n][to] != 0 && minEdge[to] > input[minVertex.n][to] {
				minEdge[to] = input[minVertex.n][to];
				queue.offer(new Vertex(to, inut[minVerted.n][to]));
			}
		}
	}
	
	
	System.out.println(result);
}

Kruskal vs Prim

• 프림은 사이클 가능성이 없음

• 크루스칼은 사이클이 이루어지는지 항상 확인 (find(a) == find(b))

• 간선의 개수가 적은 경우 크루스칼

• 간선의 개수가 많은 경우 프림