[Java] 인접행렬, 인접리스트

알고리즘 문제 풀면서 그래프를 구현할 때 Input 값에 따라 인접행렬과 인접리스트 중 어떤 걸 사용할지 정했었는데 시간복잡도와 메모리 측면에서 정확하게 어떤 상황에서 어떤 방법을 사용해야 하는지 알아보기 위해 구현방법과 개념을 정리하려고 합니다.

인접행렬

인접 행렬(Adjacency Matrix)방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식으로 자바에서는 아래와 같이 구현하여 사용할 수 있다.

/*
5 7
1 2
1 3
1 4
2 3
2 5
3 4
4 5
*/
public class 인접행렬 {

    public static StringTokenizer st;
    
    public static int[][] graph;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        
        int V = Integer.parseInt(st.nextToken());	// 노드의 수
        int E = Integer.parseInt(st.nextToken());	// 간선의 수
        
        graph = new int[V + 1][V + 1];

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());	// 시작 노드
            int e = Integer.parseInt(st.nextToken());	// 끝 노드
            graph[s][e] = 1;
        }

        for (int[] ints : graph) {
            System.out.println(Arrays.toString(ints));
        }
    }
}

 

인접행렬 방식은 연결되어 있지 않은 노드들간의 관계도 0으로 표시하기 때문에 노드 개수가 많을 수록 메모리가 불필요하게 낭비된다. 하지만 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠르다는 장점이 있다. 예를 들어 1번 노드와 5번노드와의 관계를 확인하려면 graph[1][5]만 확인하면 된다.

인접리스트

인접 리스트(Adjacency List)방식은 리스트에 각 노드가 연결된 형태를 기록하는 방식으로 자바에서는 아래와 같이 이차원 리스트로 구현할 수 있다.

/*
5 7
1 2
1 3
1 4
2 3
2 5
3 4
4 5
*/
public class 인접리스트 {

    public static StringTokenizer st;
    
    public static List<List<Integer>> graph = new ArrayList<>();

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

        int V = Integer.parseInt(st.nextToken());    // 노드의 수
        int E = Integer.parseInt(st.nextToken());    // 간선의 수

        // 노드의 수만큼 리스트 추가
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());   // 시작 노드
            int e = Integer.parseInt(st.nextToken());   // 끝 노드
            graph.get(s).add(e);
        }

        System.out.println(graph);
    }
}

 

인접리스트 방식은 서로 연결된 노드들의 정보만 리스트에 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 1번 노드에 연결된 노드를 확인하기 위해서는 graph.get(1) 리스트를 앞에서부터 차례대로 확인해야 하기 때문에 특정한 두 노드의 연결상태 정보를 얻는 속도가 느리다는 단점이 있다.

정리

	인접 행렬	인접 리스트
시간복잡도	O(N^2)     정점 N * N만큼 필요	O(N)      N : 간선의 개수
두 정점의 연결 여부	graph[x][y] 의 값으로 한번에 확인	graph<x> 의 원소에서 y가 나올때까지 탐색
인접 노드 파악 여부	N * N만큼 반복문을 돌아 확인	각 리스트에 담겨있는 원소를 확인

특정한 노드들 간의 연결 여부만 확인하면 된다면 인접행렬을 사용하는게 좋다.

특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우에는 인접리스트를 사용하는 것이 좋다.