[JAVA] 인접 리스트

인접행렬, 인접 리스트 몇번을 봐도 이해가 안 되기에 한 번 정리하고 넘어가겠다.

 

각설하고, 요점을 말하면

리스트로 구현한 그래프는 정점(vertex)를 삽입, 삭제할 일이 많을 때 사용하면 편하고,

배열로 구현한 그래프는 간선(edge)들만 추가하고 삭제할 때 사용하면 편리하다.

 

먼저, 인접 리스트란 다음과 같이 한 노드의 연결 상태를 연결 리스트로 구현한 것을 의미한다.

각 노드(정점)들의 관계를 찾고 그 노드에 해당하는 연결 리스트를 만드는 것이다.

그래프에는 여러 종류가 존재하지만 두 가지로 요약할 수 있다.

1. 가중치가 없는 그래프

2. 가중치가 있는 그래프

 

가중치가 없는 그래프는 비교적 수월하다.

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를 넣어주면서 초기화
        // 여기서의 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]

 

 

가중치가 있는 그래프는 아래와 같이 Edge 클래스를 선언하여 클래스 내에 가중치를 기억하도록 구현한다.

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