[D-16] 그래프의 표현 - 에지 리스트 & 인접 행렬 & 인접 리스트

honeypeach 2025. 2. 12. 13:07

📍 그래프

노드와 에지로 구성된 집합을 말한다.
노드는 데이터를 표현하는 단위이고 에지는 노드를 연결한다.
여러 알고리즘에서 많이 사용되는 자료구조이므로 코딩 테스트에 자주 등장한다.

✅ 에지 리스트

에지 리스트(edge list)는 에지를 중심으로 그래프를 표현한다.
에지 리스트는 배열에 출발 노드와 도착 노드를 저장하여 에지를 표현하다.
출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
벨만 포드나 크루스칼(MST) 알고리즘에 사용하며, 노드 중심 알고리즘에서는 잘 사용하지 않는다.

✅ 에지 리스트로 가중치 없는 그래프 표현하기

가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다.
노드는 여러 자료형을 사용할 수 있으며 다음의 경우 노드는 Integer형이다.

예시
- 1에서 2로 뻗어나가는 에지는 [1, 2]로 표현한다.
- 만약 방향이 없는 그래프라면 [1, 2], [2, 1]과 같이 표현한다.

✅ 에지 리스트로 가중치 있는 그래프 표현하기

가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다.

예시
- 1에서 2로 향하는 가중치가 8인 에지는 [1, 2, 8]로 표현한다.

✅ 인접 행렬

인접 행렬(adjacency matrix)은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
노드 중심으로 그래프를 표현한다.

✅ 핵심 원리

장점
- 인접 행렬을 이용한 그래프 구현은 쉽다.
- 두노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있다.

단점
- 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다. (에지 탐색을 위해 N번 접근해야 한다.)
- 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있다.
- 노드가 3만 개가 넘으면 자바 힙 스페이스(java heap space)에러가 발생한다.

✅ 인접 행렬로 가중치 없는 그래프 표현하기

1을 저장하는 이유는 가중치가 없기 때문이다.

예시
- 1에서 2로 향하는 에지가 있다는 표시를 노드 중심으로 한다고 이해햐면 된다.
- 1에서 2를 향하는 에지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다.

✅ 인접 행렬로 가중치 있는 그래프 표현하기

예시
- 2에서 5로 향하는 에지의 가중치를 2행 5열에 기록한다.

✅ 인접 리스트

인접 리스트(adjacency list)는 ArrayList로 그래프를 표현한다.
노드 개수만큼 ArrayList를 선언한다.
자료형은 경우에 맞게 사용한다.
DFS, BFS와 함께 사용된다.

✅ 핵심 원리

장점
- 노드와 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나다.
- 노드 개수가 커도 공간 효율이 좋아 메모리 초과에러도 발생하지 앟는다.
- 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.

단점
- 그래를 구현하는 다른 방법에 비해 인접 리스트를 이용한 그래프 구현은 복잡한 편이다.

✅ 인접 리스트로 가중치 없는 그래프 표현하기

인접 리스트에는 N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현한다.

예시
- 노드 1과 연결된 2, 3 노드는 ArrayList[1]에 [2, 3]을 연결하는 방식으로 표현한다.
- 노드 4와 연결된 5 노드는 ArrayList[4]에 [5]를 연결하는 방식으로 표현한다.

✅ 인접 리스트로 가중치 있는 그래프 표현하기

가중치가 있는 경우 자료형을 클래스로 사용한다.
다음은 (도착 노드, 가중치)를 갖는 Node 클래스를 선언하여 ArrayLsit에 사용한 것이다.

예시
- ArrayList[1]에 [(2, 8), (3, 3)]이 연결되어 있다. 이는 노드가 1과 2가 가중치 8 에지로, 노드 1과 3이 가중치 3 에지로 연결되어 있다는 것을 보여준다. 방향성도 고려되어 있다.

728x90