그래프

1. 그래프의 종류

  - 정점 중심으로 해결 : 인접 행렬, 인접 리스트 >> 최소 신장트리 : 프림, 최단 경로 : 다익스트라

  - 간선 중심으로 해결 : 간선 리스트 >> 최소 신장 트리 : 크루스칼, 최단 경로 : 벨만포드

  ※ 선형 자료구조(1 : 1), 비선형 자료구조(1 : N or N : N)

 

---

 

2. 그래프

  - 정점 : 그래프의 구성요소로 하나의 연결점

  - 간선 : 두 정점을 연결하는 선

  - 차수 : 정점에 연결된 간선의 수 (인접 정점의 수)

  - 트리도 그래프이다.

  - 종류

 

---

 

3. 인접 행렬

  - V x V 정방 행렬

  - 행 번호와 열 번호는 그래프의 정점에 대응

  - 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현

  - 보통 2차원 배열로 생성

  - 메모리 초과 위험

 

---

 

4. 인접 리스트

  - ArrayList<Node>[n]으로 선언 

  - 메모리 초과 위험X

  - 가중치가 없는 리스트 생성

import java.io.*;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) throws IOException{
    	// 입출력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = 4 // 정점의 개수 == 노드 갯수
        int m = 5 // 간선의 개수
        
        // 인접 리스트
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        
        // 인접 리스트로 구성한 그래프에 ArrayList를 넣어주면서 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
		/** 입력 예시
        *	1  2
        *   1  3
        *   1  4
        *   2  4
        *   3  4
        */
        for (int i = 0; i < m; i++) {
            String[] nv = br.readLine().split(" ");
            int n1 = Integer.parseInt(nv[0]);
            int n2 = Integer.parseInt(nv[1]);

            graph.get(n1).add(n2);
            graph.get(n2).add(n1);
        }

		1번 인접 리스트에서 4번 인접 리스트까지 출력
        for(int i = 1; i <= 4; i++){
        	bw.write(graph.get(i).toString());
        }
        bw.flush();
        bw.close();
    }
}


// 출력 : [2, 3, 4][1, 4][1, 4][1, 2, 3]

 

  - 가중치가 있는 리스트 생성

import java.util.ArrayList;
import java.util.Scanner;

class Edge<W, V> {
    private W weight;
    private V v;

    public void setEdge(W weight, V v) {
        this.weight = weight;
        this.v = v;
    }
}

public class Main {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = 4; // 노드의 갯수
        int m = 5; // 간선의 갯수

        ArrayList<Edge<Integer, Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new Edge<>());
        }

        for (int i = 0; i < m; i++) { // 간선의 갯수만큼 반복
            int n1 = input.nextInt(); // 노드 1
            int n2 = input.nextInt(); // 노드 2

            int weight = input.nextInt();

            graph.get(n1).setEdge(n2, weight);
            graph.get(n2).setEdge(n1, weight);
        }
    }
}