그래프의 표현

• 그래프를 구현하는 방법 3가지
  1. 에지 리스트
  2. 인접 행렬
  3. 인접 리스트

---

엣지 리스트

• 엣지를 중심으로 그래프를 표현
• 엣지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 엣지를 표현
• 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 엣지를 표현하기도 함
• 엣지 리스트는 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.

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

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

• 여기서는 방향이 있는 그래프를 예로 들었지만, 방향이 없는 그래프라면 [1,2], [2,1]은 같은 표현일 것이다.

엣지 리스트로 가중치 잇는 그래프 표현하기

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

---

인접 행렬

• 인접 행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현
• 인접 행렬은 엣지 리스트와 다르게 노드 중심으로 그래프를 표현
• 노드와 관련되어 있는 엣지를 탐색하려면 N번 접근해야하므로 노드 개수에 비해 엣지가 적을 때는 공간 효율성이 떨어진다.
• 또한, 노드 갯수가 많을 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 존재한다.

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

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

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

• 가중치가 있는 그래프는 가중치를 넣어준다.

---

인접 리스트

• 인접 리스트는 ArrayList로 그래프를 표현한다.
• 노드 갯수만큼 ArrayList를 선언한다.
• 그래프 구현은 복잡하지만, 노드와 연결되어 있는 엣지를 탐색하는 시간은 매우 뛰어나다.
• 노드 갯수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.

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

• 가중치가 없는 경우 자료형을 interger형으로 충분하다.
• ArrayList [5]로 선언
• 인접 리스트에는 N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현
• List 자료구조와 배열의 차이점 : 가변적.

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

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

---

출처 - 하루코딩