알고리즘 유형10. 그래프 이론

그래프는 다양하게 있지만, 여기선 신장트리, 그 중에서도 MST (최소신장트리)에 대해 작성해보려고 한다.

 

신장트리 spanning tree

: 그래프의 변형

 

트리는 부모 자식간의 관계, 그에 따른 차수, 높이가 있다. ex) 이진트리

 

여러 트리중에 신장트리란 각각의 정점들이 모두 연결된 트리 이다.

 

신장트리의 조건 (ST, spanning tree)

(얘는 트리이므로)

1. 가중치는 있을 수 있지만, 무향(방향X)이다.
2. cycleX ()

 

그중에 최소신장트리(MST, minimum spanning tree)는 각각의 정점들이 최소비용으로 모두 연결되는 트리 이다.

 

 MST 구현방법

1. 쿠르스칼 - 간선중심
2. 프림 - 정점 중심(간선이 많을 때 사용)

MST - 쿠르스칼

: 간선 기반 알고리즘으로 간선을 비용순으로 정렬하여 최소비용 간선부터 추가하며 MST를 구성

 

• 유니온-파인드 자료구조를 사용해서 사이클을 검사(사이클 유무), 간선정렬
• 모든 정점이 반드시 연결되어 있지 않아도 사용 가능

MST - 프림

: 정점 기반 알고리즘으로 시작정점(주로 0또는1)에서 출발해서 정점에 연결된 최소 비용 간선으로 이동하며 MST를 구성

 

• 우선순위 큐를 사용해서 가장 작은 비용의 간선을 선택
  → 가령 1번 정점에서 2개의 간선중 더 작은 비용의 간선으로 이동해서 2번정점에 도착하고, 2번 정점에 3개의 간선이 있다면, (1번의 나머지 1개 간선 + 2번의 3개 간선) 총 4개 간선 중 가장 작은 비용의 간선을 이용해서 다음 정점을 찾는다.
• 그래프가 모두 연결되어 있을 때 사용 (간선이 많을 때 사용)

추가
프림 vs 다익스트라
→ 프림은 최소신장 트리 를 찾고, 다익스트라는 출발점~도착점까지의 최단 거리 를 찾는다.
굳이 따지면 프림은 N:N 느낌이고, 다익스트라는 1:1 느낌이다.
또한, 프림은 무향그래프인 반면, 다익스트라는 가중치가 양수인 방향 그래프이다.

 

추가 문제 : 백준 1197

: 단순 MST 구현, 쿠르스칼과 프림 두개의 방법으로 풀이

package 그래프_ch10;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 프림
public class BaekJoon_1197 {

	static int V, E;
	static long sum;
	static List<List<Vertex>> adjList; // 인접 리스트
	static boolean[] visit; // 방문 체크

	// 현재 고려 대상의 간선 중 비용이 가장 작은 것을 선택
	static PriorityQueue<Vertex> pqueue = new PriorityQueue<Vertex>((e1, e2) -> e1.c - e2.c);

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		adjList = new ArrayList<>();

		for (int i = 0; i <= V; i++) { // List 의 1차 구조를 먼저 만든다. 0 dummy
			adjList.add(new ArrayList<Vertex>());
		}
		visit = new boolean[V + 1];
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			// 방향이 없으므로 양쪽 다 가능
			adjList.get(v1).add(new Vertex(v2, c));
			adjList.get(v2).add(new Vertex(v1, c));
		}

		// 풀이
		sum = 0;
		pqueue.clear();

		prim();
		System.out.println(sum);
	}

	// pqueue 에 들어가는 건 현재 방문 가능한 모든 정점
	static void prim() {
		// first vertex
		int cnt = 1;
		visit[1] = true;
		// 시작정점으로부터 갈 수 있는 모든 정점을 넣는다.
		// 이 후, 최소 비용 정점을 선택해서 또 그곳부터 갈 수 있는 모든 정점을 고려한다.
		// => pqueue 가 알아서 이전 미방문 정점 포함 최소 비용 정점을 찾아준다.
		pqueue.addAll(adjList.get(1));

		while (!pqueue.isEmpty()) {

			Vertex vertex = pqueue.poll();
			if (visit[vertex.v])
				continue; // edge 가 연결할 정점이 이미 방문한 것이면 skip

			visit[vertex.v] = true;
			sum += vertex.c;

			cnt++;
			if (cnt == V)
				break; // 정점의 수만큼 선택
			for (Vertex v : adjList.get(vertex.v)) {
				if (!visit[v.v])
					pqueue.add(v);
			}
		}
	}

	// 정점의 자료구조에 종속된 간선은 다른 정점과 비용정보만 관리
	static class Vertex {
		int v;
		int c;

		public Vertex(int v, int c) {
			this.v = v;
			this.c = c;
		}
	}
}

 

package 그래프_ch10;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 크루스칼
public class BaekJoon_1197_2 {
	static int V, E; // 정점의 개수 V(1≤V≤100,000)와 간선의 개수 E(1≤E≤200,000)
	static long sum; // long : V-1 개의 간선의 가중치를 합
	static int[] parent;
	static Edge[] edges;
	// 방문 체크 자료구조 없음.

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		parent = new int[V + 1];
		edges = new Edge[E];

		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			edges[i] = new Edge(v1, v2, c);
		}

		// 풀이
		sum = 0;

		// 간선을 최소 비용 기준으로 정렬 - 부담되는 부분
		Arrays.sort(edges, (e1, e2) -> e1.c - e2.c);
		//
		makeSet();

		int cnt = 0; // 간선의 수
		for (int i = 0; i < E; i++) { // 작은 것 부터!!
			Edge edge = edges[i];
			if (union(edge.v1, edge.v2)) {
				cnt++;
				sum += edge.c;
				if (cnt == V - 1)
					break; // 간선 수가 정점보다 하나 적으면 ( 모두 연결 )
			}
		}

		System.out.println(sum);
	}

	static void makeSet() {
		for (int i = 1; i <= V; i++) {
			parent[i] = i;
		}
	}

	static int findSet(int x) {
		if (parent[x] == x)
			return x;
		else
			return parent[x] = findSet(parent[x]);
	}

	// 서로소이면 합치고 true 리턴하도록
	static boolean union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);

		if (py == px)
			return false;

		if (px < py)
			parent[py] = px;
		else
			parent[px] = py;

		return true;
	}

	// 간선 중심이므로 간선이 두 정점과 비용 정보를 가지고 있다.
	static class Edge {

		int v1, v2, c;

		Edge(int v1, int v2, int c) {
			this.v1 = v1;
			this.v2 = v2;
			this.c = c;
		}
//	      @Override
//	      public String toString() {
//	          return "Edge [v1=" + v1 + ", v2=" + v2 + ", c=" + c + "]";
//	      }

	}
}