[JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트)

 그래프(Graph)란?

 

그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다.

 

vertex : 정점

edge : 정점과 정점을 연결하는 간선

 

아래는 대표적인 그래프 종류들의 예시다.

이러한 그래프는 인접 행렬, 인접 리스트 방식으로 표현할 수 있다.

 

 그래프 구현 - 인접 행렬

 

먼저, 행렬로 구현하는 방식을 살펴보자

 

 

정점 a와 정점 b를 잇는 간선이 있을 경우, 행렬(a,b)에 1을 표기해준다.

만약 가중치가 있는 그래프라면 1 대신 가중치를 넣을 수 있다.

기본적으로 무방향 그래프의 경우는 (a,b) (b,a)에 모두 간선 값을 넣지만, 방향 그래프같은 경우는 위의 표와 같이 방향에 맞는 간선만 표기한다.

 

ex) 정점 1과 3을 잇는 간선이 존재할 때 : graph[1][3] = 1, graph[3][1] = 1

위의 무방향 그래프를 코드로 표현해보자.

public class Main {

    public static void print(int[][] graph) {
        for (int i = 1; i < graph.length; i++) {
            for (int j = 1; j < graph.length; j++)
                System.out.print(graph[i][j]+ " ");
            System.out.println();
        }
    }

    public static void putEdge(int[][] graph, int x, int y) {
        graph[x][y] = 1;
        graph[y][x] = 1;
    }

    public static void main(String[] args) {
        int n = 5; //그래프 정점의 개수
        int[][] graph = new int[n+1][n+1]; //index를 1부터 맞추기 위해 n+1

        putEdge(graph, 1, 2);
        putEdge(graph, 1, 3);
        putEdge(graph, 1, 4);
        putEdge(graph, 2, 3);
        putEdge(graph, 2, 5);
        putEdge(graph, 3, 4);
        putEdge(graph, 4, 5);

        print(graph);

    }
}

 

 

실행 결과는 왼쪽 그림과 같다.

 

 

 

 

 그래프 구현 - 인접 리스트

 

이번엔 인접 리스트로 구현하는 방식이다.

 

해당 노드와 연결되어있는 노드들을 리스트로 쭉 붙이는 방식이다.

ArrayList를 사용하여 코드로 구현해보자.

public class Main {

    public static void print(ArrayList<ArrayList<Integer>> graph) {
        for (int i = 1; i < graph.size(); i++) {
            ArrayList<Integer> node = graph.get(i);
            System.out.print("node"+"["+i+"] : ");
            for (int j = 0; j < node.size(); j++)
                System.out.print(node.get(j)+ "->");
            System.out.println();
        }
    }

    public static void putEdge(ArrayList<ArrayList<Integer>> graph, int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }

    public static void main(String[] args) {
        int n = 5; //그래프 정점의 개수
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>()); //각 노드 별 리스트를 만들어준다.
        putEdge(graph, 1, 2);
        putEdge(graph, 1, 3);
        putEdge(graph, 1, 4);
        putEdge(graph, 2, 3);
        putEdge(graph, 2, 5);
        putEdge(graph, 3, 4);
        putEdge(graph, 4, 5);

        print(graph);

    }
}

 

 

실행 결과는 왼쪽과 같다.

 

 

 

 인접 행렬과 인접 리스트의 장단점

 

그렇다면 두 방식은 각각 어떤 장단점을 가지고 있을까?

 

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

먼저 행렬의 경우, 두 정점이 연결되있는지를 확인하는 방법이 쉽다. graph[x][y]의 값을 바로 확인해서 유무를 판단할 수 있기 때문이다. 단, 정점이 N개인 경우, 행렬을 만들기 위해선 N * N만큼의 공간이 필요하게 된다.

무방향 그래프의 경우는 절반의 공간이 낭비되는 셈이다.

 

이와 반대로 리스트의 경우, 실제 연결된 노드들만 리스트 원소에 담겨있으므로 공간 복잡도가 N(간선)이다.

다만, 두 정점 x, y가 연결되있는지 알고 싶다면 노드x 리스트로 들어가 원소 y가 있는지 처음부터 쭉 탐색해야 하므로 행렬보다 더 많은 시간이 소요된다.

 

둘 다 각각 장단점을 가지고 있으므로 상황에 따라 맞게 골라쓰면 된다.

간선이 많은 그래프의 경우, 인접 행렬을 통해 빠르게 연결 여부를 확인할 수 있다.

반면 간선이 적은 그래프의 경우는 인접 리스트를 통해 인접 노드를 빠르게 확인할 수 있다.