[JAVA] 인접 행렬과 인접 리스트

프로그래밍에서 그래프는 크게 인접 행렬과 인접 리스트로 표현할 수 있습니다. 이 두 방식은 서로 정반대의 특징을 가지고 있기 때문에 알고리즘 및 그래프의 종류에 따라 적절히 사용하여야 합니다.

 

- 인접 행렬(Adjacency Matrix)

인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식입니다. 아래와 같은 테스트 케이스를 봅시다.

0 2
1 3
2 3
3 0

무방향 그래프의 경우에는 아래와 같은 그림으로 나타낼 수 있습니다.

파란색으로 표시된 부분은 자신을 나타내고, 이때 무방향 그래프는 자신을 기점으로 대칭입니다.

노드 0과 노드 2를 잇는 간선이 있을 경우 행렬(0, 2)과 (2, 0)에 1을 표기해주는 방식입니다. (참고로, 방향 그래프의 경우에는 방향에 맞는 간선만 표기합니다.)

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 = Integer.parseInt(br.readLine()); // 노드의 수
	int E = Integer.parseInt(br.readLine()); // 연결된 간선의 수

	graph	= new int[N+1][N+1];

    for(int i=0; i<M; i++) {
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        putEdge(graph, x, y);
    }

}

 

 

 

- 인접 리스트(Adjacency Matrix)

인접 리스트 방식은 모든 노드에 연결된 노드에 대한 정보를 ArrayList 자료구조를 이용하여 표현합니다. 인접 행렬과는 달리 ArrayList는 동적 할당이므로 크기를 미리 지정하지 않아도 됩니다.

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 = Integer.parseInt(st.nextToken()); // 노드의 개수
    int E = Integer.parseInt(st.nextToken()); // 간선의 개수

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

    for (int i = 0; i < N; i++) {
        graph.add(new ArrayList<>()); //각 노드 별 리스트를 생성
    }

    for (int i = 0; i < E; i++) {
        st = new StringTokenizer(br.readline());
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());

        putEdge(graph, n1, n2);
    }
}

 

 

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

인접 행렬은 graph[x][y] 값을 바로 확인함으로써 두 노드 x, y가 연결되어 있는지의 여부를 파악하기 쉽습니다. 단, 노드가 N개인 경우, 행렬을 만들기 위해서는 N * N 만큼의 공간이 필요하게 됩니다. O(N^2)

 

인접 리스트의 경우, 실제 연결된 노드들만 리스트에 담겨 있으므로 공간 복잡도는 O(E)가 됩니다. 하지만 두 정점 x, y가 연결되어 있는지 여부를 확인하기 위해선 정점 x의 리스트로 들어가 원소 y가 있는지 처음부터 탐색해야 하므로 행렬보다 더 많은 시간이 소요됩니다.

 

간선이 많은 그래프의 경우 인접 행렬을 통해 연결 여부를 빠르게 확인할 수 있는 반면, 간선이 적은 그래프의 경우에는 인접 리스트를 통해 인접한 노드를 빠르게 확인할 수 있습니다. 

 

---

References

• https://velog.io/@lifeisbeautiful/Java-%EA%B7%B8%EB%9E%98%ED%94%84%EB%A5%BC-%ED%83%90%EC%83%89%ED%95%98%EA%B8%B0-%EC%9C%84%ED%95%9C-%EC%9D%B8%EC%A0%91-%ED%96%89%EB%A0%AC%EA%B3%BC-%EC%9D%B8%EC%A0%91-%EB%A6%AC%EC%8A%A4%ED%8A%B8
• https://born2bedeveloper.tistory.com/42