그래프, 인접행렬과 인접리스트

그래프 (Graph)

수학적 정의로 그래프는 객체들의 쌍들이 서로 연관되어 객체의 집합을 이루는 구조를 의미합니다.

쉽게 설명하면?

사물이나 추상적인 개념 간의 연결 관계를 표현한 것이라고 할 수 있습니다.

도시를 연결하는 도로망이나 사람들 간의 관계, 웹 사이트 링크 관계 등이 이에 해당하는 예시입니다.

 

 

그래프의 구성 요소

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

 

그래프의 종류

• 무방향 그래프 : 간선을 통해 양방향으로 이동할 수 있는 그래프 => G(A, B) == G(B, A) 동일
• 방향 그래프 : 간선에 방향이 존재하는 그래프 => G(A, B) != G(B,A) 다름
• 가중치 그래프 : 간선에 비용 또는 가중치가 할당된 그래프 => '네트워크' 라고도 함
• 연결 그래프 : 무방향 그래프에서 모든 정점쌍들에 대해 항상 경로가 존재하는 그래프
• 비연결 그래프 : 무방향 그래프에서 특정 정점쌍들에 경로가 존재하지 않는 그래프
• 순환 그래프 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우   * 단순경로란, 반복되는 정점이 없는 경로
• 비순환 그래프 : 순환이 없는 그래프

 

인접 행렬과 인접 리스트

그래프를 구현하여 표현하는 방법에는 여러가지가 있습니다.

일반적으로 인접행렬과 인접리스트 방식이 있습니다.

이 두 가지 방식은 서로 정반대의 특징을 갖기 때문에, 한 방식의 장점이 다른 방식의 단점이 되는 경우가 나타납니다.

따라서,

구현하려는 알고리즘, 그래프의 종류에 따라 적절하게 사용하여야 합니다.

 

 

1. 인접 행렬 그래프 - "모든 정보를 저장"

• 직관적이며 쉽게 구현이 가능합니다.
• 하지만, 불 필요한 정보의 저장이 많으며, 그래프의 크기가 커지면서 메모리 초과가 발생할 수도 있습니다.

구현방법은 int 형 2차원 배열을 주로 이용하며, 이동할 수 있다면 1, 이동할 수 없다면 0으로 표기합니다.

 

ㅓㅏㅣㅓㅏㅣㅓㅏㅣㅓㅏㅣㅓ

 

인덱스를 가지고 그래프 예시를 들자면, 아래와 같이 생각하면 됩니다.

https://freestrokes.tistory.com/87

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

 

위에서 설명한 인접 행렬을 코드로 구현해보겠습니다.

class ArrGraph {

    private int[][] arrGraph;

    public ArrGraph(int initSize) {

        /*
            배열의 idx 가 0부터 시작함으로, ArrayIndexOutOfBoundException 방지를 위해
            정점을 담는 인접행렬의 행과 열 size 는 1을 더하여 초기화 해줌.
         */

        this.arrGraph = new int[initSize+1][initSize+1];
    }

    public int[][] getArrGraph() {
        return this.arrGraph;
    }

    public void putTwoWay(int x, int y) {
        arrGraph[x][y] = arrGraph[y][x] = 1;
    }

    public void putOneWay(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 AdjArray {
    public static void main(String[] args) {
        int initSize = 6;
        ArrGraph adjArr = new ArrGraph(initSize);

        adjArr.putTwoWay(1, 2);
        adjArr.putTwoWay(1, 3);
        adjArr.putTwoWay(2, 3);
        adjArr.putTwoWay(2, 4);
        adjArr.putTwoWay(3, 4);
        adjArr.putTwoWay(3, 5);
        adjArr.putTwoWay(4, 5);
        adjArr.putTwoWay(4, 6);
        
        adjArr.printGraphToAdjArr();
    }
}

---

2. 인접 리스트 그래프

• 필요한 정보만 저장하여, 메모리 절약이 가능합니다.
• 하지만, 인접행렬에 비해 다소 어려움이 있습니다.

인접리스트는 배열(ArrayList)이나, 연결리스트(LinkedList) 등의 자료구조를 이용하여, 각 정점에서 이동가능한 정점들을 저장합니다.

대표적으로 두 자료구조를 이용한 2차원 배열이라고 생각할 수 있습니다.

아래도 위와 같이 인덱스를 가지고 예시를 들어보자면,

 

1	2 ->	3
2	1 ->	3 ->	4
3	1 ->	2 ->	4 ->	5
4	2 ->	3 ->	5 ->	6
5	3 ->	4 ->
6	4 ->

 

위 상황을 코드로 구현로 나타내보겠습니다.

 

import com.sun.scenario.effect.impl.sw.java.JSWBlend_SRC_OUTPeer;

import java.util.ArrayList;

class ListGraph {
    private ArrayList<ArrayList<Integer>> listGraph;

    public ListGraph(int initSize) {
        this.listGraph = new ArrayList<ArrayList<Integer>>();

        // 안에있는 값들을 초기화를 해줍니다. 그렇지만 +1 필수!
        for (int i = 0; i < initSize + 1; i++) {
            listGraph.add(new ArrayList<>());
        }
    }

    public ArrayList<ArrayList<Integer>> getGraph() {
        return this.listGraph;
    }
    public ArrayList<Integer> getNode(int i ) {
        return this.listGraph.get(i);
    }

    // 그래프 추가 (양방향)
    public void putTwoWay(int x, int y) {
        listGraph.get(x).add(y);
        listGraph.get(y).add(x);
    }

    // 그래프 추가 (단방향)
    public void putOneWay(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 AdjList {
    public static void main(String[] args) {
        int initSize = 6;
        ListGraph adjList = new ListGraph(initSize);

        // 단방향
        // 따로..
        
        
        // 양방향
        adjList.putTwoWay(1, 2);
        adjList.putTwoWay(1, 3);
        adjList.putTwoWay(2, 3);
        adjList.putTwoWay(2, 4);
        adjList.putTwoWay(3, 4);
        adjList.putTwoWay(3, 5);
        adjList.putTwoWay(4, 5);
        adjList.putTwoWay(4, 6);
        
        //System.out.println(adjList.getGraph());
        adjList.printGraphToAdjList();
    }
}

---

 

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

인접행렬

• 정점 v1, v2에 대해 한 번의 접근으로 확인 가능합니다
• V개의 노드 표현을 위해 V 제곱 만큼의 공간이 필요합니다.
• 인접 노드를 찾기 위해선, 모든 노드를 순회해야 합니다.
• 공간 복잡도는 O(V제곱) 입니다.

인접리스트

• 리스트의 처음부터 하나 씩 확인해야 합니다.
• V개의 리스트에 간선(E) 만큼 원소가 들어 있습니다.
• 인접 노드를 쉽게 찾을 수 있습니다.
• 공간 복잡도는 O(V + E) 입니다.