[Algorithm] 그래프 알고리즘 비교(MST, kruskal, prim, dijkstra, floyd-warshall, bellman-ford)

.compare Graph Algorithms

.MST(Minimum Spanning Tree), 최소신장트리

정점 -1개의 간선으로 이루어진 신장트리 중에서 가중치의 합이 가장 작은 것

고르는 간선은 사이클을 만들지 않아야 하고, 가중치가 작은 것들부터 골라져야 함

* 절대적이진 않지만, 

  간선이 적으면 KRUSKAL, 간선이 많으면 PRIM 알고리즘이 유리

---

.KRUSKAL

(간선을 고르는 간선 중심)

MST 의 목적을 이루기 위해 간선들을 가중치 오름차순으로 정렬해두고,

사이클을 만들지 않는 간선이라면 골라나가서 N-1 개를 고르면 완료

참고

ㅇ Use edgeList

public class MST_Kruskal_Test {
 
    static class Edge implements Comparable<Edge> {
        int from, to, weight;
 
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
 
    static int V, E;
    static Edge[] edgeList;
    static int[] parents;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader in = 
            new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine(), " ");
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        edgeList = new Edge[E];
        parents = new int[V];
 
        // 각 간선 및 가중치에 대한 정보(간선의 가중치)
        int from, to, weight;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());
 
            edgeList[i] = new Edge(from, to, weight);
        }
        // 최초, 모든 간선을 가중치 기준 오름차순으로 정렬
        Arrays.sort(edgeList);
        // 정점 초기화
        make();
        // 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가
        int cnt = 0, res = 0;
        for (Edge edge : edgeList) {
            // 싸이클이 형성되지 않았다면
            if (union(edge.from, edge.to)) {
                res += edge.weight;
                // N-1개의 간선이 선택될 때까지 반복
                if (++cnt == V - 1) break;
            }
        }
        
        System.out.println(res);
    }
 
    // 정점 초기화(자신을 대표자로)
    private static void make() {
        for (int i = 0; i < V; i++) {
            parents[i] = i;
        }
    }
    // Find : Path Compression
    private static int find(int a) {
        if (a == parents[a]) return a;
        return parents[a] = find(parents[a]);
    }
    // Union
    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        // 사이클 존재 시 false
        if (aRoot == bRoot) return false;
        // 사이클이 생성되지 않는다면(다른 부모를 갖는다면) Union 수행
        parents[bRoot] = aRoot;
        return true;
    }
}

ㅇ use priorityQueue immediately

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class MST_Kruskal_Test {
 
    static int N, parents[];
    static PriorityQueue<Edge> pq;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        parents = new int[N];
        pq = new PriorityQueue<>();
        
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < N; j++) {
                int weight = Integer.parseInt(st.nextToken());
                if(i < j) pq.add(new Edge(i, j, weight));
            }
        }
 
        System.out.println(prim());
    }
 
    private static long prim() {
        
        long res = 0;
        int cnt = 0;
        
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
        
        while(!pq.isEmpty()) {
            Edge now = pq.poll();
            if(union(now)) {
                res += now.w;
                if(++cnt == N - 1) return res;
            }
        }
        
        return res;
    }
 
    private static boolean union(Edge now) {
        
        int aRoot = find(now.from);
        int bRoot = find(now.to);
        
        if(aRoot == bRoot) return false;
        
        parents[bRoot] = aRoot;
        return true;
        
    }
 
    private static int find(int n) {
        
        if(n == parents[n]) return n;
        return parents[n] = find(parents[n]);
        
    }
 
    static class Edge implements Comparable<Edge> {
        int from, to, w;
 
        public Edge(int from, int to, int w) {
            this.from = from;
            this.to = to;
            this.w = w;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.w, o.w);
        }
        
    }
}
 

---

.Prim

(정점을 고르는 정점중심)

MST 목적을 이루기 위해 정점들을 선택된 집합과 선택되지 않은 집합으로 나누고,

선택된 집합으로부터 뻗어나가 선택되지 않은 집합의 정점으로 이어지는 간선중에

제일 작은 것을 골라나가며(해당 정점이 선택집합으로 편입) 모두 편입되면 완료

참고

ㅇ 인접 행렬

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class MST_Prim_Test {
 
    static class Node implements Comparable<Node> {
        // 목적지
        int no;
        // 비용
        int edge;
        public Node(int no, int edge) {
            super();
            this.no = no;
            this.edge = edge;
        }
        @Override
        public int compareTo(Node o) {
            return this.edge - o.edge;
        }
    }
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine().trim());
        int[][] input = new int[cnt][cnt];
        boolean[] visited = new boolean[cnt];
        int[] minEdge = new int[cnt];
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
 
        StringTokenizer st;
        for (int i = 0; i < cnt; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < cnt; j++) {
                input[i][j] = Integer.parseInt(st.nextToken());
            }
            minEdge[i] = Integer.MAX_VALUE;
        } // i노드에서 j노드까지의 비용을 모두 배열에 저장
 
        int result = 0, nodeCount = 0;
        minEdge[0] = 0;
        queue.offer(new Node(0, 0));
 
        while (!queue.isEmpty()) {
 
            // 일단 꺼내자. 그럼 젤 작은애가 나오겠찌.
            Node minVertex = queue.poll();
            // 근데 그 나온애가 이미 목적지가 확보된 녀석이라면 패스.
            if (visited[minVertex.no]) continue;
 
            // 확보되지 않은애가 나왔으면 고르자.
            result += minVertex.edge;
            visited[minVertex.no] = true;
            if (++nodeCount == cnt) break;
 
            for (int j = 0; j < cnt; j++) {
                // 새로 확보된 녀석으로부터 출발하는 간선을 다 PQ에 넣는다.
                if (!visited[j] && input[minVertex.no][j] != 0 && input[minVertex.no][j] < minEdge[j]) {
                    minEdge[j] = input[minVertex.no][j];
                    queue.offer(new Node(j, input[minVertex.no][j]));
                }
            }
        }
        System.out.println(result);
    }
 
}

ㅇ 인접 리스트

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class MST_Prim_Test {
 
    static int V, E;
    static ArrayList<Node>[] adj;
    static class Node implements Comparable<Node> {
        int to, weight;
 
        public Node(int to, int weight) {
            super();
            this.to = to;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        V = Integer.parseInt(st.nextToken());    // 정점 개수
        E = Integer.parseInt(st.nextToken());    // 간선 개수
        
        adj = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            adj[i] = new ArrayList<>();
        }
        
        // Edge 정보 입력
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            // 인접 리스트
            adj[a].add(new Node(b, c));
            adj[b].add(new Node(a, c));
        }
        
        System.out.println(prim());
    }
 
    private static long prim() {
        
        boolean[] visited = new boolean[V + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 1번 노드부터 출발
        pq.add(new Node(1, 0));
        
        long res = 0;
        int cnt = 0;
        while(!pq.isEmpty()) {
            
            Node edge = pq.poll();
            // 이미 확인한 정점이면 pass
            if(visited[edge.to]) continue;
            
            res += edge.weight;
            visited[edge.to] = true;
            // 모든 노드를 방문했다면 return
            if(++cnt == V) return res;
            
            for (int i = 0; i < adj[edge.to].size(); i++) {
                // 연결된 노드들 중 방문하지 않은 노드 찾기
                Node next = adj[edge.to].get(i); 
                if(visited[next.to]) continue;
                
                pq.add(next);
            }
        }
        
        return res;
    }
 
}
 
 
출처: https://data-make.tistory.com/519 [Data Makes Our Future]

---

.최단 경로

정점으로부터 정점까지의 모든 경로 중에서 가장 비용이 작은 경로

.Dijkstra

(정점을 고르는 정점 중심)

출발 정점으로부터 다른 모든 정점까지의 거리를

선택된 정점을 지나서 가는 경우와 직접 가는 경우 중 최솟값을 갱신해가면서

가장 가까운 정점을 하나씩 선택된 정점에 편입시켜가며 최단경로를 갱신

음의 가중치를 허용하지 않음

참고

적용 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Dijkstra_Test {
 
    static class Edge implements Comparable<Edge> {
        int v, weight;
 
        public Edge(int v, int weight) {
            this.v = v;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());    // 정점의 개수
        int E = Integer.parseInt(st.nextToken());    // 간선의 개수
        int K = Integer.parseInt(br.readLine()) - 1;    // 시작 정점(번호를 1부터 input)
        final int INF = Integer.MAX_VALUE;
        
        // 인접 리스트 준비
        List<Edge>[] adj = new ArrayList[V];
        for (int i = 0; i < V; i++) 
            adj[i] = new ArrayList<>();
        
        // 간선 정보 입력
        for (int i = 0; i < E; i++)  {
            st = new StringTokenizer(br.readLine());
            adj[Integer.parseInt(st.nextToken()) - 1].add(new Edge(Integer.parseInt(st.nextToken()) - 1, 
                    Integer.parseInt(st.nextToken())));
        }
    
        // dist 배열
        int[] dist = new int[V];
        boolean[] checked = new boolean[V];
        
        // dist 배열을 INF로 초기화
        Arrays.fill(dist, INF);
        // 시작점은 0으로 변경
        dist[K] = 0;
        
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.add(new Edge(K, 0));
        Edge cur = null;
        
        while(!pQ.isEmpty()) {
            // check되지 않았으면서,
            // 현재(i)정점으로부터 dist 값이 제일 작은 정점(j)의 번호 찾기
            cur = pQ.poll();
            if(checked[cur.v]) continue;
            
            // 찾은 정점(j)으로부터 갈 수 있는 경로가 이미 알고 있는 dist보다 작다면 갱신
            // index가 가지고 있는 모든 간선을 검사
            for (Edge next : adj[cur.v]) {
                // check되지 않았으면서 다음 노드 까지의 거리가
                // 나까지 거리 + 나로부터 다음 노드까지 거리보다 작다면 갱신 
                if(!checked[next.v] && dist[next.v] > dist[cur.v] + next.weight) {
                    dist[next.v] = dist[cur.v] + next.weight;
                    pQ.add(new Edge(next.v, dist[next.v]));
                }
            }
            
            // 체크 완료
            checked[cur.v] = true;
        }
        
        for (int i = 0; i < V; i++) {
            if(dist[i] == INF) System.out.println("INF");
            else System.out.println(dist[i]);
        }
    }
}

---

.Floyd-Warshall

모든 정점들에 대한 최단 경로

참고

import java.util.Scanner;
 
public class FloydWarshall_Test {
 
    static final int INF = 987654321;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        int[][] adjMatrix = new int[N][N];
 
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                adjMatrix[i][j] = sc.nextInt();
                // 자기자신으로의 인접 정보가 아니고 인접해있지 않다면 INF로 채우기
                if (i != j && adjMatrix[i][j] == 0) {
                    adjMatrix[i][j] = INF;
                }
            }
        }
 
        // 경유지 -> 출발지 -> 도착지
        for (int k = 0; k < N; ++k) {
            for (int s = 0; s < N; ++s) {
                // 출발지와 경유지가 같다면 pass
                if (s == k) continue; 
                
                for (int e = 0; e < N; ++e) {
                    // 경유지와 목적지가 같거나 출발지가 곧 목적지라면 pass
                    if (s == e || k == e) continue; 
                    
                    // 경유한 길이 최단 거리라면 갱신
                    if (adjMatrix[s][k] + adjMatrix[k][e] < adjMatrix[s][e]) 
                        adjMatrix[s][e] = adjMatrix[s][k] + adjMatrix[k][e];
                }
            }
            for(int i=0; i<N; ++i) {
                for(int j=0; j<N; ++j) {
                    System.out.print(adjMatrix[i][j]+"\t");
                }
                System.out.println();
            }
            System.out.println("=====================================");
    
        }
 
    }
 
}

---

.Bellman-Ford

다익스트라 알고리즘과 동일하지만 벨먼-포드 알고리즘은 음의 가중치 허용

참고