그래프(Graph) 인접 리스트(adjacency list)로 구현하기

그래프와 DFS BFS에 대한 설명은 이전 포스팅을 참고 ☞ 그래프(Graph)와 BFS, DFS

---

그래프(Graph) 구현하기

그래프를 구현하는 방법은 크게 2가지가 있습니다. 인접 행렬(adjacency matrix)로 구현하는 방법과 인접 리스트(adjacency list)로 구현하는 방법이 있습니다. (간선(edge)이 많은 경우 인접 행렬(adjecency matrix)로 구현하는 것이 좋고, 아닌 경우 인접리스트로 구현하는 것이 유리하다 라고 알고 있습니다만 간선이 '많다'의 기준을 저는 잘 모르겠습니다. 공부해야 할 영역입니다.) 이 포스팅에서는 인접 리스트로 구현해 보도록 하겠습니다.

인접 리스트(adjacency list)로 그래프 구현하기

노드(정점)들의 연결 관계를 어떤 식으로 저장해 두는 지가 그래프 구현의 핵심입니다. 인접 리스트로 구현 시에는 노드 각각의 리스트를 생성하고, 연결되어 있는 노드들을 리스트에 담아둡니다. 위의 그래프의 노드 연결 관계를 인접 리스트로 표현하면 아래와 같습니다.

0이 연결 되어있는 1와 4를 하나의 리스트에 담고, 1이 연결 되어있는 0,4,2,3를 또 하나의 리스트에 담습니다. 이런 식으로 각 노드들이 어떤 노드들과 연결되어 있는지 저장 해둘 수 있습니다.

코드로 구현하기(java)

먼저 Node(노드) 클래스를 구현합니다. 각 노드는 값과, 인접되어 연결되어 있는 노드들을 담을 list가 필요합니다.

class Node{
    int data; //노드의 값
    LinkedList<Node> adjacent; //인접되어 연결되어 있는 노드들
}

그리고 Graph(그래프) 클래스를 구현합니다. 각 노드들을 담고 있는 배열을 하나 선언 해줍니다.

class Graph{
    Node[] nodes;
}

노드와 그래프의 기본적은 필드 값은 위와 같습니다. 노드들을 추가하거나, 엣지(간선)을 추가하는 메소드는 아래와 같습니다. (코드의 구현은 절대적인 정답은 없습니다. 각 클래스의 필드를 힌트 삼아서 직접 작성해보는 것도 많은 도움이 됩니다.)

class Graph{
    Node[] nodes;

    //인덱스와 노드의 데이터가 같다고 정함   
    public void setNode(){
    for (int i = 0; i <nodesSize; i++) {
            nodes[i] = new Node(i);
        }
    }

    //엣지 추가하기
    void addEdge(int i1, int i2) {
        Node n1 = nodes[i1];
        Node n2 = nodes[i2];

        //지금 추가되지 않은 경우만
        if (!n1.adjacent.contains(n2)) { 
            //리스트에 추가
            n1.adjacent.add(n2);
        }
    }
}

---

DFS 탐색 구현 방법은 다음 포스팅 참고 ☞ 그래프(Graph) DFS 탐색 구현하기