그래프

인접 행렬, 인접 리스트

인접 행렬

package basic.graph;

import java.util.ArrayDeque;

public class Graph_Martix {
    static boolean[][] martix=new boolean[5][5];
    static boolean[] visit = new boolean[5];
    public static void main(String[] args) {
        martix[1][2] = true;
        martix[1][4] = true;
        martix[2][3] = true;
        martix[2][4] = true;
        martix[3][2] = true;
        martix[4][3] = true;

//        dfs(1);
        bfs(1);
    }

    static void dfs(int n){
        visit[n] = true;
        System.out.print(n+"--> ");

        for (int i=1;i<=4;i++){
            if(!martix[n][i] || visit[i]) continue;
            dfs(i);
        }
    }

    static void bfs(int n){
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(n);
        visit[n] = true;

        while(!q.isEmpty()){
            int v = q.poll();

            System.out.print(v+"--> ");

            for (int i=1;i<=4;i++){
                if(!martix[v][i] || visit[i]) continue;
                visit[i] = true;
                q.add(i);
            }
        }
    }
}

인접 리스트

package basic.graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Graph_AdjList {
    static List<List<Integer>> adjList = new ArrayList<>();
    static boolean[] visit = new boolean[5];
    public static void main(String[] args) {
        for(int i=0; i<=4;i++){
            adjList.add(new ArrayList<Integer>());
        }
        adjList.get(1).add(2);
        adjList.get(1).add(4);
        adjList.get(2).add(3);
        adjList.get(3).add(2);
        adjList.get(4).add(3);


        dfs(1);
//        bfs(1);
    }

    static void dfs(int n){
        visit[n] = true;
        System.out.print(n+"--> ");

        for(Integer i : adjList.get(n)){
            if(visit[i]) continue;
            dfs(i);
        }
    }

    static void bfs(int n){
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(n);
        visit[n] = true;

        while(!q.isEmpty()){
            int v = q.poll();

            System.out.print(v+"--> ");

            List<Integer> list = adjList.get(v);
            for(Integer i : list){
                if(visit[i]) continue;
                visit[i] = true;
                q.add(i);
            }
        }
    }
}

		// 단순 반복은 원하는 정렬된 항목을 얻을 수 없다.
//		for (Node node : pq) {
//			System.out.println(node);
//		}
	}
	
	static class Node{
		int y, x;
		Node(int y, int x){
			this.y = y; this.x = x;
		}
		
		@Override
		public String toString() {
			return "Node [y=" + y + ", x=" + x + "]";
		}
	}	

//	static class Node implements Comparable<Node>{
//		int y, x;
//		Node(int y, int x){
//			this.y = y; this.x = x;
//		}
//		
//		@Override
//		public String toString() {
//			return "Node [y=" + y + ", x=" + x + "]";
//		}
//
//		@Override
//		public int compareTo(Node o) {
//			return o.y - this.y;
//		}
//	}
}

MST

크루스칼 알고리즘

// 간선 리스트의 모든 간선을 비용 기준으로 정렬 ( 오름 차순 )
// 가장 비용이 적은 간선부터 차례대로 선택해 간다.
// 간선 선택 시 사이클이 발생 X <= Union Find 알고리즘 이용
// 간선 중심 풀이

package basic.graph;

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

public class MST_Kruscal {
    static int V,E,sum;
    static Edge[] edges;
    static int[] parent;
    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());

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

        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);
        }

        Arrays.sort(edges, (e1,e2) -> e1.c-e2.c);
        for(int i=0;i<V;i++){
            parent[i] = i;
        }

        int cnt = 0;

        for(int i=0;i<edges.length;i++){
            Edge edge = edges[i];
            // 사이클이 아니면 선택
            if(union(edge.v1, edge.v2)){
                System.out.println(edge.v1+"->"+edge.v2);
                sum += edge.c;
                cnt++;
                if(cnt == V-1) break;
            }
        }

        System.out.println(sum);
    }

    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 v1+", "+v2+", c:"+c;
        }
    }

    static int find(int x){
        return parent[x]==x? x : (parent[x]=find(parent[x]));
    }

    static boolean union(int a, int b){
        a = find(a);
        b = find(b);

        if(a==b) return false;
        else parent[b] = a;

        return true;
    }
}

prim

// 시작 정점에서부터 가장 비용이 적은 다른 정점을 계속 선택해 간다.
// 이 때 선택의 대상은 이미 선택된 모든 정점으로부터 갈 수 있는 선택되지 않은 정점
// 가장 비용이 적은 다른 정점을 선택 <= PriorityQueue 를 이용
// 정점 중심 풀이

package basic.graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Vector;

public class MST_Prim {
    static int V, sum;
    static int[][] matrix;
    static boolean[] visit;
    static PriorityQueue<Vertex> pq = new PriorityQueue<>( (v1,v2)-> v1.c-v2.c);

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

        V = Integer.parseInt(br.readLine());
        matrix = new int[V][V];
        visit = new boolean[V];

        for(int i=0;i<V;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<V;j++){
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        pq.offer(new Vertex(0,0)); // 0이 시작 정점
        int cnt = 0;

        while(!pq.isEmpty()){
            Vertex vertex = pq.poll(); // 비용이 가장 작은 개체
            if(visit[vertex.v]) continue;

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

            if(cnt==V) break;

            for(int i=0;i<V;i++){
                if(matrix[vertex.v][i] == 0 || visit[i]) continue;
                pq.offer(new Vertex(i, matrix[vertex.v][i]));

            }
        }

        System.out.println(sum);
    }

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