그래프의 표현
그래프를 구현하는 3가지 방법
에지 리스트
에지 리스트는 에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 1. 에지 리스트로 가중치가 없는 그래프 표현
가중치가 없으므로 출발 노드와 도착 노드만 표현하므로 배열의 행 2개면 표현이 가능하다.
에지 리스트로 가중치가 있는 그래프 표현
행을 3개로 늘려 3번째 행에 가중치를 저장한다.
1에서 2로 향하는 가중치가 8이면 [1, 2, 8]로 표현한다.
인접 행렬
인접 행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
인접 행렬로 가중치 없는 그래프 표현하기
2차원 배열을 생성하고, 1에서 2를 향하는 에지의 표현은 (1, 2) = 1로 표현한다. 1로 저장하는 이유는 가중치가 없기 때문이다. 1에서 2로 향하는 에지가 있다는 표시를 한다고 이해한다.
인접 행렬로 가중치가 있는 그래프 표현하기.
1번과 다르게 가중치를 대입한다. 3에서 4로 가는 비용이 13이면 (3, 4) = 13 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 시간 복잡도가 좋지 않다.
노드 개수가 많을 경우 인접 행렬로 구현하는 것을 피하자.
🌟 인접 리스트
인접 리스트는 ArrayList로 그래프를 표현한다. 노드 개수만큼 리스트를 선언한다.
인접 리스트로 가중치가 없는 그래프 표현하기
가중치가 없으면 Integer의 ArrayList의 배열로 선언한다.
ArrayList<Integer>[5]
배열의 장점은 index를 통해 직접 접근이 가능하다.
예를들어 3 -> 4로 가는 가중치가 없는 노드가 있다면, A = ArrayLIst<Integer>[N] 일 때, A[3].add(4)로 표현한다.
인접 리스트가 가중치가 있는 그래프로 표현하기
가중치가 있는 경우 (도착 노드, 가중치)를 갖는 Class를 선언하여 ArrayList에 넣어준다.
3 -> 4로 가는 가중치 13을 가진 에지 표현
A[3].add(new Node(4, 13))
그래프의 구현은 복잡한 편이지만, 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어난다.
동적으로 생성되기 때문에 빈 공간이 발생하지 않고, 공간 효율이 좋아서 메모리 초과 에러도 발생하지 않는다.
Last updated