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

그래프

그래프란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조입니다.

그래프에서 쓰이는 용어는

• 정점 (vertex) : 노드라고도 하며 데이터가 저장되는 원소
• 간선 (edge) : 링크라고도 하며 정점 간의 관계
• 그외에도 인접 정점, 차수, 경로 등의 용어가 있습니다.

 

 

 

그래프 구현

그래프를 구현하는 방법은 배열(Array)을 사용하는 인접 행렬, 연결 리스트를 사용하는 인접 리스트가 있습니다.

 

인접 행렬

그래프의 정점을 2차원 배열로 만들어서, 행과 열은 정점을 의미하며 각각의 원소들은 정점 간의 간선을 나타냅니다.

장점

• 2차원 배열에 모든 장점들의 간선 정보가 있기 때문에 두 정점을 연결하는 간선을 조회 시 O(1)의 시간복잡도로 가능합니다.
• 구현이 비교적 간단합니다.

단점

• 간선 수와 무관하게 항상 n^2 크기의 2차원 배열이 필요하여 메모리 공간이 낭비됩니다.
• 그래프의 모든 간선의 수를 알아내려면 인접 행렬 전체를 확인해야하므로 O(n²) 의 시간이 소요됩니다. 

 

자바 구현

package ch11;

public class 인접행렬 {
    private int[][] matrixGraph;    // 연결은 1, 연결되지 않은 노드끼리는 0

    // 생성자로 초기화
    public AdjacencyMatrix(int initSize) {
        // 배열의 인덱스는 0부터 시작이므로 행과 열 size +1로 초기화
        this.matrixGraph = new int[initSize + 1][initSize + 1];
    }

    // 그래프 리턴
    public int[][] getMatrixGraph() {
        return this.matrixGraph;
    }

    // 그래프 추가 (양방향)
    public void put (int x, int y) {
        matrixGraph[x][y] = matrixGraph[y][x] = 1;
    }

    // 그래프 추가 (단방향)
    public void putSingle (int x, int y) {
        matrixGraph[x][y] = 1;
    }
    // 그래프 출력 (인접 행렬)
    public void printAdjacencyMatrix() {
        for (int i=0; i<matrixGraph.length; i++) {
            System.out.print(i+ "| ");

            for (int j=0; j<matrixGraph[i].length; j++) {
                System.out.print(" " + matrixGraph[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int initSize = 6;
        인접행렬 adjMatrix = new 인접행렬(initSize);

        adjMatrix.put(1, 2);
        adjMatrix.put(1, 3);
        adjMatrix.put(2, 3);
        adjMatrix.put(2, 4);
        adjMatrix.put(3, 4);
        adjMatrix.put(3, 5);
        adjMatrix.put(4, 5);
        adjMatrix.put(4, 6);

        adjMatrix.printAdjacencyMatrix();
    }
}

 

 

인접 리스트

그래프의 각 정점에 인접한 정점들을 연결리스트로 표현하는 방법이다.

즉 정점의 개수만큼 인접리스트가 존재하며, 각각의 인접리스트에는 인접한 정점 정보가 저장되는 것이다.

그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.

 

장점

• 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다.
• 그래프의 모든 간선의 수를 알아내거나 특정 정점에 접근하려면 각 정점의 헤더 노드부터 연결된 모든 인접 리스트를 탐색해야하므로 O(V+E)의 시간이 소요된다.

 

단점

• 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야하므로 정점의 차수만큼의 시간이 필요하다. O(degree(v))
• 구현이 비교적 어렵다.

 

자바 구현 (가중치가 없는 양방향 그래프)

public class 인접리스트 {
    private ArrayList<ArrayList<Integer>> listGraph;

    //그래프 초기화 (생성자 이용)
    public 인접리스트(int initSize) {
        this.listGraph = new ArrayList<ArrayList<Integer>>();
        // 노드는 0부터 시작하므로 반복문을 길이+1까지 돌도록 한다.
        // 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>());
    }

    // 그래프 리턴
    public ArrayList<ArrayList<Integer>> getListGraph() {
        return this.listGraph;
    }
    // 그래프 추가(양방향)
    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 printListGraph() {
        for (int i=0; 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 static void main(String[] args) {
        int initSize = 6;
        인접리스트 adjList = new 인접리스트(initSize);

        adjList.put(1, 2);
        adjList.put(1, 3);
        adjList.put(2, 3);
        adjList.put(2, 4);
        adjList.put(3, 4);
        adjList.put(4, 5);
        adjList.put(4, 6);

        adjList.printListGraph();
    }
}

 

 

 

참고
https://freestrokes.tistory.com/87
https://suyeon96.tistory.com/32#---%--%EA%B-%B-%EB%-E%--%ED%--%--%--%EA%B-%AC%ED%--%--%---%--%EC%-D%B-%EC%A-%--%--%EB%A-%AC%EC%-A%A-%ED%-A%B-%---Adjacency%--List-