인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) - JAVA

그래프의 연결관계를 나타내는 방식은 인접 행렬과 인접 리스트로 두 가지의 방법이 있습니다.

 

인접 행렬(Adjacency Matrix)

---

인접 행렬은 이차원 배열을 이용하여 그래프를 표현하는 방식입니다.

출처 : https://www.programiz.com/dsa/graph-adjacency-matrix

위 의 그림과 같이 2 차원 배열의 형태로 두 노드의 번호를 좌표로 이용하여 1이면 연결이 되었음을 0이면 연결 되지 않았음을 뜻하게 됩니다.

 

무방향 그래프의 경우 양방향으로 연결 되기 때문에 아래와 같이 두 좌표에 입력을 합니다.

graph[i][j] = 1

graph[j][i] = 1

 

방향 그래프의 경우 한쪽에서만 연결 되기 때문에 한 좌표에만 입력을 합니다.

graph[i][j] = 1

 

장단점

• 장점
  • 구현이 쉬움
  • 노드의 연결성을 확인할 때 시간 복잡도는 O(1)로 빠름
• 단점
  • 간선의 수와 상관 없이 항상 n² 크기의 2차원 배열을 사용하기 때문 메모리 낭비가 있음
  • 모든 간선의 수를 찾기 위해 2차원 배열을 모두 확인 할 때의 시간 복잡도는 O(n²)

구현

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

for(int i = 0; i < M; i++) {
    int u = sc.nextInt();
    int v = sc.nextInt();

    graphMap[u][v] = 1;
    graphMap[v][u] = 1;
}

 

인접 리스트(Adjacency List)

---

인접 리스트는 리스트를 이용하여 그래프를 표현하는 방식입니다.

출처 : https://www.programiz.com/dsa/graph-adjacency-list

노드의 개수만큼 인접리스트를 생성하고 각 인접리스트에는 인접한 노드의 번호를 저장합니다.

 

장단점

• 장점
  • 인접 행렬과 달리 간선의 수에 따라 데이터의 크기가 정해지기 때문에 메모리 낭비가 없음
  • 모든 간선의 수를 알아낼 때 각 노드의 헤더 노드부터 연결된 모든 인접리스트를 탐색 시간 복잡도는 O(V+E) V = 노드의 수, E = 엣지의 수
• 단점
  • 두 노드를 연결하는 간선을 조회하거나 노드의 차수를 알기 위해서는 노드의 인접 리스트를 탐색해야 하므로 노드의 차수만큼의 시간이 필요

구현

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

for(int i = 0; i <= N; i++) {
    graphList.add(new ArrayList<>());
}

for(int i = 0; i < M; i++) {
    int u = sc.nextInt();
    int v = sc.nextInt();

    graphList.get(u).add(v);
    graphList.get(v).add(u);
}