Day-14 그래프의 표현

---

1. 에지 리스트

• 에지를 중심으로 그래프를 표현한다.
• 구현이 쉽다.
• 특정 노드와 관련되어 있는 에지를 탐색하기가 어렵다.
• 벨만 포드, 크루스칼 알고리즘에 사용한다.

 

가중치가 없는 그래프인 경우 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다.

1에서 2로 가는 에지는 [1, 2]로 표현한다.

 

가중치가 있는 그래프인 경우 배열에 출발 노드, 도착 노드, 가중치를 저장하여 에지를 표현한다.

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

---

2. 인접 행렬

• 2차원 배열을 자료구조로 이용하여 노드 중심으로 그래프를 표현한다.
• 구현이 쉽다.
• 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
• 노드 개수가 많은 경우 사용할 수 없다.

 

노드 개수가 5이므로 5 x 5 행렬을 사용한다.

1에서 2로 가는 에지는 A[1][2]에 1을 저장하여 표현한다.

가중치가 없는 그래프이므로 가중치 대신 1을 저장한다.

 

가중치가 있는 그래프이면 1 대신 가중치를 저장한다.

1에서 2로 가는 가중치가 8인 에지는 A[1][2]에 8을 저장하여 표현한다.

---

3. 인접 리스트

• ArrayList로 그래프를 표현한다.
• 구현이 복잡하다.
• 공간 효율성이 좋다.

 

노드 개수인 5만큼 ArrayList를 선언한다.

1과 연결된 노드 2, 3을 ArrayList[1]에 [2, 3]을 연결하여 표현한다.

 

가중치가 있는 그래프인 경우 도착 노드, 가중치를 갖는 Node 클래스를 사용한다.

1과 연결된 노드 2, 3을 ArrayList[1]에 [(2, 8), (3, 3)]을 연결하여 표현한다.

---

4. 예제 문제

---

[2178] 미로 탐색 (JAVA)