⚡ 그래프 심화 (2)
📌 Prim 알고리즘
🔷 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
1) 임의 정점을 하나 선택해서 시작
2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3) 모든 정점이 선택될 때 까지 1), 2) 과정을 반복
💡 값은 무한대(자료형의 최댓값)로, 부모는 -1로 정점 배열을 초기화 해둔다. 그리고 출발 정점은 0으로 바꾼다. 값이 가장 작은 정점을 찾아 해당 정점을 방문했음을 표시하고 그 정점과 인접하면서 갱신이 가능한 정점들을 찾아간다. 찾은 정점들의 값에 가중치를 넣고 부모에 이전 정점을 넣는다. 이후 뽑지 않은 정점들 중 가장 작은 값을 찾으며 이전 과정을 반복하는데 인접 정점이 부모와 값이 이미 있더라도 넣을 수 있는 값이 기존의 값보다 작으면 새로운 값과 부모로 수정한다.
💡 크루스칼과 마찬가지로 어떤 정점으로 시작한들 방문 순서만 달라질 뿐 가중치의 합은 같다.
❗ 부모 정보는 필요 없을 수도 있다.
🔷 서로소인 2개의 집합 정보를 유지
트리 정점들(tree vertices): MST를 만들기 위해 선택된 정점들비트리 정점들(nontree vertices): 선택되지 않은 정점들
🖥 인접행렬로 구현
import java.util.Scanner;
public class DailyAPS {
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(input);
int V = sc.nextInt(); //7 이 들어오는데 0~6
int E = sc.nextInt();
//인접 행렬
int [][] adjArr = new int[V][V];
for(int i = 0; i < E; i++) {
int A = sc.nextInt();
int B = sc.nextInt();
int W = sc.nextInt();
adjArr[A][B] = W;
adjArr[B][A] = W;
}
//정점은 뽑혔거나 안뽑혔거나 두가지 상태 boolean[]
boolean [] visited = new boolean[V];
int [] p = new int[V]; //부모
int [] dist = new int[V]; //key(값)을 저장하는 용도
for(int i = 0; i < V; i++) {
p[i] = -1;
dist[i] = INF;
}//초기화
//또는 Arrays.fill(dist, INF); Arrays.fill(p, -1);
//임의의 한점을 선택해서 돌려야한다.
dist[0] = 0; //이것이 가장 먼저 뽑히게 세팅
int ans = 0;
//프림 동작
for(int i = 0; i < V-1; i++) {
//1. 값이 가장 작은 정점을 뽑는다.
int min = INF;
int idx = -1;
//순회하면서 인뽑은 정점들중 가장 작은 값 뽑기
for(int j = 0; j < V; j++) {
if(!visited[j] && dist[j] < min) {
min = dist[j];
idx = j;
}
}
//위의 반복문이 끝나고 뽑힌 값이 가장 적은 정점을 방문했음을 표시한다.
visited[idx] = true;
//이 정점의 값은 확정이니 정답에 더한다.
ans += dist[idx];
//2. 뽑은 정점과 인접한 정점들 중 갱신 가능한 정점은 모두 갱신
for(int j = 0; j < V; j++) {
if(!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]) {
dist[j] = adjArr[idx][j];
p[j] = idx;
}
}
}
System.out.println(ans);
}
static String input = "7 11\r\n" +
"0 1 32\r\n" +
"0 2 31\r\n" +
"0 5 60\r\n" +
"0 6 51\r\n" +
"1 2 21\r\n" +
"2 4 46\r\n" +
"2 6 25\r\n" +
"3 4 34\r\n" +
"3 5 18\r\n" +
"4 5 40\r\n" +
"4 6 51\r\n" +
"\r\n";
}🖥 우선순위 큐로 구현
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class DailyAPS {
static final int INF = Integer.MAX_VALUE;
//시작점,끝점,가중치를 담은 간선 클래스
static class Edge implements Comparable<Edge>{
int st, ed, w;
public Edge(int st, int ed, int w) {
this.st = st;
this.ed = ed;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return this.w - o.w;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(input);
int V = sc.nextInt();
int E = sc.nextInt();
List<Edge>[] adjList = new ArrayList[V];
//초기화
for(int i = 0; i < V; i++)
adjList[i] = new ArrayList<>();
for(int i = 0; i < E; i++ ) {
int A = sc.nextInt();
int B = sc.nextInt();
int W = sc.nextInt();
adjList[A].add(new Edge(A, B, W));
adjList[B].add(new Edge(B, A, W));
}
//방문처리
boolean[] visited = new boolean[V];
PriorityQueue<Edge> pq = new PriorityQueue<>();
//시작정점을 하나 뽑고 넣어놓고 시작
visited[0] = true;
for(int i = 0; i < adjList[0].size(); i++) {
pq.add(adjList[0].get(i));
}
//다른 방법 1
// for(Edge e : adjList[0])
// pq.add(e);
//다른 방법 2
// pq.addAll(adjList[0]);
int pick = 1; //이미 정점을 하나 뽑았으니까
int ans = 0;
while(pick != V) {
Edge e = pq.poll();
if(visited[e.ed]) continue; //모두 다 넣었으니까...
ans += e.w;
pq.addAll(adjList[e.ed]);
visited[e.ed] = true;
pick++;
}
System.out.println(ans);
}
static String input = "7 11\r\n" +
"0 1 32\r\n" +
"0 2 31\r\n" +
"0 5 60\r\n" +
"0 6 51\r\n" +
"1 2 21\r\n" +
"2 4 46\r\n" +
"2 6 25\r\n" +
"3 4 34\r\n" +
"3 5 18\r\n" +
"4 5 40\r\n" +
"4 6 51\r\n" +
"\r\n";
}둘 다 결과값은 175 로 잘 나온다.
📌 다익스트라(Dijkstar) 알고리즘
🔷 최단 경로
- 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
- 하나의 시작 정점에서 끝 정점까지의 최단 경로
1)다익스트라 알고리즘(음의 가중치 허용 X)
2)벨만-포드(Bellman-Ford) 알고리즘(음의 가중치 허용 O) - 모든 정점들에 대한 최단 경로
플로이드-워샬(Floyd-Warshall)알고리즘
🔷 다익스트라 알고리즘
- 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
- 그리디 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.
- 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다.
- 이 때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다.
🔷 동작 과정
1) 시작 정점을 입력 받는다.
2) 거리를 저장할 D 배열을 무한(자료형의 최댓값)으로 초기화 한 후 시작점에서 갈 수 있는 곳의 값은 바꿔 놓는다.
3) 아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치의 합이 작다면 변경하여 적는다.
4) 모든 정점을 방문할 때까지 반복
💡 프림과 다른 점이라면 누적합의 최소를 찾는다.
❗ 다익스트라는 근시안 적인 관점의 알고리즘으로, 음의 가중치가 있을 때에는 사용할 수 없다.
🖥 다익스트라 구현
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class DailyAPS {
static final int INF = Integer.MAX_VALUE;
static int V, E;//정점의 수, 간선의 수
static List<Node>[] adjList;//인접리스트
static int[] dist;//최단 길이를 저장할 배열
//도착정점과 가중치를 담은 노드
static class Node{
int v, w;
public Node(int v, int w) {
this.v = v;
this.w = w;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(input);
V = sc.nextInt();
E = sc.nextInt();
adjList = new ArrayList[V];
for(int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
dist = new int [V];
Arrays.fill(dist, INF);
for(int i = 0; i < E; i++) {
int A = sc.nextInt(); //시작정점
int B = sc.nextInt(); //도착정점
int W = sc.nextInt(); //가중치
//유향 그래프
adjList[A].add(new Node(B, W)); //인접리스트에 노드 추가
}
dijkstra(0);
System.out.println(Arrays.toString(dist));
}
static void dijkstra(int start) {
//방문을 표시할 배열 선언
boolean [] visited = new boolean[V];
dist[start] = 0; //시작 정점까지의 거리는 0으로 초기화
for(int i = 0; i < V-1; i++) {
int min = INF;
int idx = -1;
//선택하지 않은 정점 중 dist가 가장 작은 값을 고르기
for(int j = 0; j < V; j++) {
if(!visited[j] && min > dist[j]) {
min = dist[j];
idx = j;
}
}
if(idx == -1) break; //선택할 정점이 없으면 break
visited[idx] = true; //선택
for(int j = 0; j < adjList[idx].size(); j++) {
Node curr = adjList[idx].get(j);
//방문하지 않았고, 연결 되어있으면서 (인접리스트라 확인하지 않아도 된다.)
//이미 가지고 있는 값보다 갱신할 여지가 있으면 갱신한다.
if(!visited[curr.v] && dist[curr.v] > dist[idx]+curr.w) {
dist[curr.v] = dist[idx] + curr.w;
}
}
}
}
static String input = "6 11\r\n" + "0 1 4\r\n" + "0 2 2\r\n" + "0 5 25\r\n" + "1 3 8\r\n" + "1 4 7\r\n"
+ "2 1 1\r\n" + "2 4 4\r\n" + "3 0 3\r\n" + "3 5 6\r\n" + "4 3 5\r\n" + "4 5 12\r\n" + "";
}
Hodie mihi, Cras tibi