[자료 구조] 자바를 이용한 그래프의 구현-인접 리스트 구현 :: Graph implementation by using adjacency List in java.

인접 리스트

인접 리스트는 그래프의 각 정점에 인접한 정점을 연결 리스트로 표현하는 방법이다.
연결 리스트의 노드는 인접 정점 정보를 저장하는데, 그래프에는 이러한 각 인접 리스트에 대한 헤더 포인터를 갖는 배열로 갖는다.
이 말은 정점의 번호만 알고 있으면 각 정점의 연결 리스트에 쉽게 접근 가능하다는 소리와 같다.

위의 그림과 같이 연결되어있는 관계를 리스트로 표현하는 것이다.

인접 리스트의 특징

n개의 노드가 있다면 n^2만큼의 메모리 양이 필요했던 인접 행렬과 달리, 인접 리스트는 필요한 만큼만의 메모리를 잡아먹는다. 또한 노드를 탐색하는 것도 상수에 가까운 시간이 걸리지만 어떤 노드i와 j의 연결 상태를 보려면 모든 원소를 돌아야 하기 떄문에 오래 걸린다는 단점이 있다.

인접 리스트의 구현

class Adjacency_List {
    private LinkedList<Object>[] adjLists;
    private int vertex;

    private static class GraphNode {
        int vertex;
        GraphNode link;
    }

    GraphNode[] head = new GraphNode[10];
    int totalVertex = 0;

    void  insertVertex(int v){
        totalVertex ++;
    }

    void insertEdge(int v1, int v2) {
        if(totalVertex <= v1 || totalVertex <= v2){
            System.out.println("그래프에 없는 정점 입니다.");
        }else {
            GraphNode node = new GraphNode();
            node.vertex = v2;
            node.link = head[v1];
            head[v1] = node;
            
        }
    }
}