MST
Spanning Tree
- 그래프 내의 모든 정점을 포함하는 트리이다.
Minimum Spanning Tree
- 그래프의 최소 연결 부분 그래프이다.
- n개의 정점을 가지고 있다면, 최소 간선의 수는 (n-1)개이다.
Prim’s Algorithm
특징
- 정점 선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법
구현
배열
W : G의 인접 행렬
nearest[] : vi에 가장 가까운 정점 Y의 인덱스
distance[] : nearest[i] 의 정점과 v 사이의 가중치
구현 - java
package prim;
public class prim {
static int inf = Integer.MAX_VALUE;
public static class vertex{
int a,b;
vertex(int a, int b)
{
this.a = a;
this.b = b;
}
}
public static void main(String[] args)
{
int W[][] = {{},{0,0,1,3,inf,inf},{0,1,0,3,6,inf},{0,3,3,0,4,2},{0,inf,6,4,0,5},{0,inf,inf,2,5,0}};
vertex F[] = new vertex[W.length];
F = prim(5,W,F);
System.out.println(1);
}
/*
n : vertex의 개수
F : edge의 집합
*/
public static vertex[] prim(int n, int W[][], vertex[] F)
{
int i, vnear=0, min, edge;
int[] nearest = new int[n+1];
int[] distance = new int[n+1];
int IF = 0;
/* 1. 초기화 */
for(i=2;i<=n;i++)
{
nearest[i] = 1;
distance[i] = W[1][i];
}
/* 2 */
for(int j=1;j<n;j++)
{
min = inf;
for(i=2;i<=n;i++)
{
if(0<=distance[i] && distance[i]<min)
{
min = distance[i];
vnear = i;
}
}
F[IF++] = new vertex(vnear, nearest[vnear]);
distance[vnear] = -1;
for(i=2;i<=n;i++)
{
if(W[i][vnear] < distance[i]){
distance[i] = W[i][vnear];
nearest[i] = vnear;
}
}
}
return F;
}
}
1. nearest, distance 배열 초기화
| 1 | 2 | 3 | 4 | 5 | |
| nearest[] | 1 | 1 | 1 | 1 | |
| distance[] | 1 | 3 | inf | inf |
2. 간선은 n-1 개 만들어지므로, n-1번 반복을 한다.
- min 변수를 inf로 초기화 한다.
- 인접한 꼭짓점을 찾기위해 distance[] 에서 0보다 크고 min보다 작은 값을 찾는다.
- min을 inf로 설정을 해두었기 때문에, 방문하지 못하는 곳은 걸러진다.
- 찾은 값을 min으로 해두고, vnear 값에 index를 저장한다.
- 찾은 vnear 값과, nearest[v]의 값을 F에 저장해준다.
- distance 배열의 vnear 값을 음수로 변경하여, e 의 비교과정을 스킵되게 한다.
- W[i][vnear]이 distance[i]보다 작다면, distance 값을 갱신해주고, nearest[i] 값을 vnear로 변경해준다.
Kruskal’s Algorithm
그래프 간선들을 가중치의 오름차순으로 정렬해 놓은 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택한다.
- 그래프 간선을 오름차순 순서대 정렬한다.
- 가장 작은 간선을 선택한다.
- 다음 간선을 선택한다
- 만약 다음 간선을 선택했을 때, 간선 간 사이클이 형성이 된다면, 선택하지 않는다.
- 선택된 간선의 개수가 정점의 개수 n 보다 1 작게되면, 종료한다.
package kruskal;
import java.util.List;
import java.util.Scanner;
public class Kruskal {
static Edge E[];
static int[] set;
static final int INF = Integer.MAX_VALUE;
static class Edge{
int a;
int b;
int distance;
Edge(int a, int b, int distance)
{
this.a = a;
this.b = b;
this.distance = distance;
}
}
static int inf = Integer.MAX_VALUE;
public static void main(String[] args)
{
int N, M;
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); M = sc.nextInt();
E = new Edge[M];
for(int i=0;i<M;i++)
{
E[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
}
sortE(E);
set = new int[N];
for(int i=0;i<N;i++) set[i] = i;
int distance_sum = 0;
for(int i=0; i<M;i++){
if(!find(E[i].a-1, E[i].b-1)){
distance_sum += E[i].distance;
unionParent(E[i].a-1, E[i].b-1);
}
}
System.out.println(1);
}
public static void sortE(Edge E[])
{
for(int i = 1; i < E.length; i++)
{
for(int j = 1; j <= E.length - i; j++)
{
if(E[j-1].distance > E[j].distance){
swap(j-1,j);
}
}
}
}
public static void swap(int i, int j)
{
Edge tmp = E[i];
E[i] = E[j];
E[j] = tmp;
}
public static int getParent(int x)
{
if(set[x] == x) return x;
return set[x] = getParent(set[x]);
}
public static void unionParent(int a, int b)
{
a = getParent(a);
b = getParent(b);
if(a<b) set[b] = a;
else set[a] = b;
}
public static boolean find(int a, int b)
{
a = getParent(a);
b = getParent(b);
if(a==b) return true;
else return false;
}
}
MST
Spanning Tree
- 그래프 내의 모든 정점을 포함하는 트리이다.
Minimum Spanning Tree
- 그래프의 최소 연결 부분 그래프이다.
- **n**개의 정점을 가지고 있다면, 최소 간선의 수는 **(n-1)**개이다.
- Undirected graph $G = (V,E)$
- V : set of vertices / $V = \{v_1,v_2,v_3,v_4,v_5\}$
- E : set of edges / $E = \{(v_1, v_2), (v_1, v_3), (v_2,v_4),(v_3,v_4),(v_3,v_5),(v_4,v_5)\}$
flowchart TD
v1((v1))
v2((v2))
v3((v3))
v4((v4))
v5((v5))
v1---|1|v2
v2---|3|v3
v2---|6|v4
v3---|4|v4
v5---|2|v3
v5---|5|v4
v1---|3|v3
Prim’s Algorithm
특징
- 정점 선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법
구현
배열
W : G의 인접 행렬
$W[i][j] = \begin{cases} weight~on~edge~~~if~there~is~an~edge~from~v_i~to~v_2 \\ \infty ~if~there~is~no~edge~from~v_i~to~v_j\\0~if~i=j \end{cases}$
nearest[] : $v_i$에 가장 가까운 정점 $Y$의 인덱스
distance[] : nearest[i] 의 정점과 v 사이의 가중치
구현 - java
package prim;
public class prim {
static int inf = Integer.MAX_VALUE;
public static class vertex{
int a,b;
vertex(int a, int b)
{
this.a = a;
this.b = b;
}
}
public static void main(String[] args)
{
int W[][] = {{},{0,0,1,3,inf,inf},{0,1,0,3,6,inf},{0,3,3,0,4,2},{0,inf,6,4,0,5},{0,inf,inf,2,5,0}};
vertex F[] = new vertex[W.length];
F = prim(5,W,F);
System.out.println(1);
}
/*
n : vertex의 개수
F : edge의 집합
*/
public static vertex[] prim(int n, int W[][], vertex[] F)
{
int i, vnear=0, min, edge;
int[] nearest = new int[n+1];
int[] distance = new int[n+1];
int IF = 0;
/* 1. 초기화 */
for(i=2;i<=n;i++)
{
nearest[i] = 1;
distance[i] = W[1][i];
}
/* 2 */
for(int j=1;j<n;j++)
{
min = inf;
for(i=2;i<=n;i++)
{
if(0<=distance[i] && distance[i]<min)
{
min = distance[i];
vnear = i;
}
}
F[IF++] = new vertex(vnear, nearest[vnear]);
distance[vnear] = -1;
for(i=2;i<=n;i++)
{
if(W[i][vnear] < distance[i]){
distance[i] = W[i][vnear];
nearest[i] = vnear;
}
}
}
return F;
}
}
- nearest, distance 배열 초기화
1 2 3 4 5
| nearest[] | 1 | 1 | 1 | 1 | |
| distance[] | 1 | 3 | inf | inf |
- 간선은 n-1 개 만들어지므로, n-1번 반복을 한다.
- min 변수를 inf로 초기화 한다.
- 인접한 꼭짓점을 찾기위해 distance[] 에서 0보다 크고 min보다 작은 값을 찾는다.
- min을 inf로 설정을 해두었기 때문에, 방문하지 못하는 곳은 걸러진다.
- 찾은 값을 min으로 해두고, vnear 값에 index를 저장한다.
- 찾은 vnear 값과, nearest[v]의 값을 F에 저장해준다.
- distance 배열의 vnear 값을 음수로 변경하여, e 의 비교과정을 스킵되게 한다.
- W[i][vnear]이 distance[i]보다 작다면, distance 값을 갱신해주고, nearest[i] 값을 vnear로 변경해준다.
Kruskal’s Algorithm
그래프 간선들을 가중치의 오름차순으로 정렬해 놓은 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택한다.
- 그래프 간선을 오름차순 순서대 정렬한다.
- 가장 작은 간선을 선택한다.
-
- 만약 다음 간선을 선택했을 때, 간선 간 사이클이 형성이 된다면, 선택하지 않는다.다음 간선을 선택한다
- union-find를 통해 사이클을 확인한다.
- 선택된 간선의 개수가 정점의 개수 n 보다 1 작게되면, 종료한다.
package kruskal;
import java.util.List;
import java.util.Scanner;
public class Kruskal {
static Edge E[];
static int[] set;
static final int INF = Integer.MAX_VALUE;
static class Edge{
int a;
int b;
int distance;
Edge(int a, int b, int distance)
{
this.a = a;
this.b = b;
this.distance = distance;
}
}
static int inf = Integer.MAX_VALUE;
public static void main(String[] args)
{
int N, M;
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); M = sc.nextInt();
E = new Edge[M];
for(int i=0;i<M;i++)
{
E[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
}
sortE(E);
set = new int[N];
for(int i=0;i<N;i++) set[i] = i;
int distance_sum = 0;
for(int i=0; i<M;i++){
if(!find(E[i].a-1, E[i].b-1)){
distance_sum += E[i].distance;
unionParent(E[i].a-1, E[i].b-1);
}
}
System.out.println(1);
}
public static void sortE(Edge E[])
{
for(int i = 1; i < E.length; i++)
{
for(int j = 1; j <= E.length - i; j++)
{
if(E[j-1].distance > E[j].distance){
swap(j-1,j);
}
}
}
}
public static void swap(int i, int j)
{
Edge tmp = E[i];
E[i] = E[j];
E[j] = tmp;
}
public static int getParent(int x)
{
if(set[x] == x) return x;
return set[x] = getParent(set[x]);
}
public static void unionParent(int a, int b)
{
a = getParent(a);
b = getParent(b);
if(a<b) set[b] = a;
else set[a] = b;
}
public static boolean find(int a, int b)
{
a = getParent(a);
b = getParent(b);
if(a==b) return true;
else return false;
}
}
'알고리즘' 카테고리의 다른 글
| String Matching [Navie, DFA, KMP] (0) | 2023.01.24 |
|---|