Java 인접행렬과 인접리스트를 이용하여 그래프 구현하기

Java 인접행렬과 인접리스트를 이용하여 그래프 구현하기

Java로 인접행렬과 인접리스트를 만들어 그래프를 구현하는 방법에 대해 알아보겠습니다.

1. 그래프 (Graph)

수학적 정의로 그래프는 객체들의 쌍들이 서로 연관되어 객체의 집합을 이루는 구조를 의미합니다. 쉽게 설명하면 사물이나 추상적인 개념간의 연결 관계를 표현한 것이라고 할 수 있습니다. 도시를 연결하는 도로망이나 사람들 간의 관계, 웹 사이트의 링크 관계 등이 이에 해당하는 예시 입니다.

그래프에 대해서는 많은 내용들이 있지만 이번 포스팅에서는 간단하게 정리하여 알아보겠습니다.

1.1 그래프의 구성요소

그래프의 구성요소를 간단하게 정리하면 다음과 같습니다.

• 정점 (Vertex / Node)
  그래프에서 위치를 나타냅니다.
• 간선 (Edge / Link / Branch)
  그래프에서 위치간의 관계를 나타냅니다. 즉, 각 정점(노드)를 연결하는 선을 의미합니다.
  
• 인접 정점 (Adjacent Vertex)
  간선(Edge)에 의해 직접 연결된 정점을 의미합니다.
  
• G(V, E)
  그래프는 정점과 간선의 집합이므로 G(V, E)는 그래프 자체를 의미합니다.

1.2 그래프의 종류

그래프에는 다음과 같이 여러 종류가 있습니다.

• 무방향 그래프
  간선을 통해 양방향으로 이동할 수 있는 그래프
  G(A,B)는 G(B,A)와 동일

• 방향 그래프
  간선에 방향이 존재하는 그래프
  G(A,B)와 G(B,A)는 다름

• 가중치 그래프
  간선에 비용 또는 가중치가 할당된 그래프
  '네트워크' 라고도 함

• 연결 그래프
  무방향 그래프에서 모든 정점쌍들에 대해 항상 경로가 존재하는 그래프
  

• 비연결 그래프
  무방향 그래프에서 특정 정점쌍들에 경로가 존재하지 않는 그래프

• 순환 그래프
  단순 경로의 시작 정점과 종료 정점이 동일한 경우
  ※ 단순 경로(Simple Path) : 반복되는 정점이 없는 경로

• 비순환 그래프
  순환이 없는 그래프

2. 인접 행렬과 인접 리스트

그래프를 구현하여 표현하는 방법에는 여러가지가 있지만 일반적으로 인접행렬과 인접리스트 방식이 있습니다. 이 두가지 방식은 서로 정반대의 특징을 갖기 때문에 한 방식의 장점이 다른 방식의 단점이 되는 경우가 나타납니다. 따라서 구현하려는 알고리즘, 그래프의 종류에 따라 적절하게 사용하여야 합니다.

아래는 그래프의 예시이며 표는 그래프의 정점과 정점간의 관계에 대해 나타낸 것입니다.

정점	인접 정점
1	2
1	3
2	3
3	4
2	4
4	5
3	5
4	6

위의 그래프를 대상으로 인접 행렬과 인접 리스트를 이용한 그래프의 구현에 대해 알아보겠습니다.

2.1 인접 리스트를 이용한 그래프 구현

아래는 각 정점마다 이어지는 간선의 목록을 표현한 것입니다. 각 정점마다 각각의 연결 리스트를 갖게 하는 방식으로 표현되었습니다.

다음은 ArrayList를 사용하여 구현한 양방향 인접리스트 소스코드입니다.

import java.util.ArrayList;
 
/*
 * @ TITLE Adjacency List (인접리스트)
 */
 
// 그래프(리스트) 클래스
class ListGraph {
    private ArrayList<ArrayList<Integer>> listGraph;
 
    // 그래프 초기화
    public ListGraph(int initSize) {
        this.listGraph = new ArrayList<ArrayList<Integer>>(); // 그래프 생성
        
        // 그래프 초기화
        // put(int x, int y) 에서 입력되는 정점의 값은 0 이상의 정수이나
        // ArrayList의 index는 0 부터 시작이므로 
        // ArrayIndexOutOfBoundsException 방지를 위해 
        // 정점을 담는 인접리스트의 size는 1을 더하여 초기화해줌
        // ex) initSize = 3
        // graph[0]
        // graph[1] -> 2 -> 3
        // graph[2] -> 1 -> 3 -> 4
        // graph[3] -> 1 -> 2 -> 4 -> 5
        for(int i=0; i<initSize+1; i++) {
            listGraph.add(new ArrayList<Integer>());
        }
    }
 
    // 그래프 return
    public ArrayList<ArrayList<Integer>> getGraph() {
        return this.listGraph;
    }
 
    // 그래프의 특정 노드 return
    public ArrayList<Integer> getNode(int i) {
        return this.listGraph.get(i);
    }
 
    // 그래프 추가 (양방향)
    public void put(int x, int y) {
        listGraph.get(x).add(y);
        listGraph.get(y).add(x);
    }
 
    // 그래프 추가 (단방향)
    public void putSingle(int x, int y) {
        listGraph.get(x).add(y);
    }
    
    // 그래프 출력 (인접리스트)
    public void printGraphToAdjList() {
        for(int i=1; i<listGraph.size(); i++) {
            System.out.print("정점 " + i + "의 인접리스트");
            
            for(int j=0; j<listGraph.get(i).size(); j++) {
                System.out.print(" -> " + listGraph.get(i).get(j));
            }
            System.out.println();
        }
    }
}
 
public class AdjacencyList {
    
    public static void main(String[] args) {
        int initSize = 6;
        ListGraph adjList = new ListGraph(initSize);
        
        adjList.put(1, 2);
        adjList.put(1, 3);
        adjList.put(2, 3);
        adjList.put(2, 4);
        adjList.put(3, 4);
        adjList.put(3, 5);
        adjList.put(4, 5);
        adjList.put(4, 6);
        
        adjList.printGraphToAdjList();
    }
    
}

실행 결과는 다음과 같습니다.

2.2 인접 행렬을 이용한 그래프 구현

인접 행렬은 NxN 행렬로 graph[i][j]가 true라면 정점 i 에서 정점 j 로의 간선이 있다는 것을 의미합니다. 정점의 개수가 V 라면 V^2 크기의 2차원 배열을 생성하여 1과 0을 사용하여 true/false를 구분하여 값을 저장합니다. 양방향 인접행렬의 경우 대칭 행렬의 형태로 구성됩니다.

ex) 2번 정점에서 4번 정점으로의 간선이 존재할 경우

• 단뱡항 : graph[2][4] = 1
• 양방향 : graph[2][4] = graph[4][2] = 1

다음은 2차원 배열을 사용하여 구현한 양방향 인접행렬 소스코드입니다.

/*
 * @ TITLE Adjacency Array (인접행렬)
 */
 
// 그래프(행렬) 클래스
class ArrGraph {
    private int[][] arrGraph;
 
    // 그래프 초기화
    public ArrGraph(int initSize) {
        // 그래프 초기화
        // put(int x, int y) 에서 입력되는 정점의 값은 0 이상의 정수이나
        // 배열의 index는 0 부터 시작이므로 
        // ArrayIndexOutOfBoundsException 방지를 위해 
        // 정점을 담는 인접행렬의 행과 열 size는 1을 더하여 초기화해줌
        this.arrGraph = new int[initSize+1][initSize+1];
    }
 
    // 그래프 return
    public int[][] getGraph() {
        return this.arrGraph;
    }
 
    // 그래프 추가 (양방향)
    public void put(int x, int y) {
        arrGraph[x][y] = arrGraph[y][x] = 1;
    }
 
    // 그래프 추가 (단방향)
    public void putSingle(int x, int y) {
        arrGraph[x][y] = 1;
    }
    
    // 그래프 출력 (인접행렬)
    public void printGraphToAdjArr() {
        for(int i=0; i<arrGraph.length; i++) {
            for(int j=0; j<arrGraph[i].length; j++) {
                System.out.print(" " + arrGraph[i][j]);
            }
            System.out.println();
        }
    }
}
 
public class AdjacencyArray {
    
    public static void main(String[] args) {
        int initSize = 6;
        ArrGraph adjArr = new ArrGraph(initSize);
        
        adjArr.put(1, 2);
        adjArr.put(1, 3);
        adjArr.put(2, 3);
        adjArr.put(2, 4);
        adjArr.put(3, 4);
        adjArr.put(3, 5);
        adjArr.put(4, 5);
        adjArr.put(4, 6);
        
        adjArr.printGraphToAdjArr();
    }
    
}

실행 결과는 다음과 같습니다.

인접 행렬에 가중치(weight)를 추가할 경우 간선이 존재하는 행렬에 1 대신 가중치 값을 설정해주면 됩니다.

// 그래프 추가 (양방향 가중치)
public void put(int x, int y, int w) {
    // 1 대신 가중치 값 w(weight)를 설정
    arrGraph[x][y] = arrGraph[y][x] = w;
}

3. 인접 행렬과 인접 리스트의 차이

인접 행렬과 인접 리스트의 차이를 간단하게 정리하면 다음과 같습니다.

	정점 간의 간선 여부	공간 복잡도
인접 행렬	정점 v1, v2에 대해 한 번의 접근으로 확인 가능	V개의 노드 표현을 위해 V^2 만큼의 공간이 필요  인접 노드를 찾기 위해선 모든 노드를 순회해야 함  공간복잡도 : O(V^2)
인접 리스트	리스트의 처음부터 하나씩 확인해야 함	V개의 리스트에 간선(E) 만큼 원소가 들어있음  인접 노드를 쉽게 찾을 수 있음  공간복잡도 : O(V+E)

또한 인접 행렬과 인접 리스트가 사용되는 경우는 다음과 같습니다.

• 인접 행렬 : 그래프에 간선이 많이 존재하는 밀집 그래프
• 인접 리스트 : 그래프에 간선이 적게 존재하는 희소 그래프

이상으로 Java 인접 행렬과 인접 리스트를 이용하여 그래프를 구현하는 방법에 대해서 알아봤습니다.

※ 참고 문헌

• gmlwjd9405.github.io, [자료구조] 그래프(Graph)란, https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

• ko.wikipedia.org, 그래프, https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84

• manduku.tistory.com, 자료구조 Graph - 그래프의 정의와 표현 By java, https://manducku.tistory.com/21

• blog.devjoshua.me, Java 인접리스트 구현하기, http://blog.devjoshua.me/2018/10/01/java-adjacency-list/

• tramyu.github.io, 자료구조 - Graph, https://tramyu.github.io/data/algorithm-graph/