11-2. 그래프의 표현

256P ~278P

강의: 08-1

 

---

< 그래프의 표현>

---

■ 에지 리스트

      - 에지를 중심으로 그래프를 표현

 

 ✔ 가중치가 없는 그래프 표현

      - 그래프는 출발 노드와 도착 노드만 표현

      - 배열의 행은 2개면 충분

      - 노드는 여러 자료형을 사용할 수 있다

 

예) Integer형

 

 ✔ 가중치가 있는 그래프 표현

      - 배열의 행을 3개로 늘린다

      - 3번째 행에 가중치를 저장한다

 

* 방향이 없는 그래프인 경우에는 시작 노드를 두지 않고 시작

** 특정 노드와 관련되어 있는 에지를 탐색하기 어렵다

 

■ 인접 행렬

      - 2차원 배열 자료구조를 이용하여 그래프를 표현

      - 노드 중심 그래프 표현

 

 ✔ 가중치가 없는 그래프 표현

 ✔ 가중치가 있는 그래프 표현

*N번 접근을 해야 하므로 시간복잡도가 좋진 않다

 

■ 인접 리스트 ❗❗❗

      - 노드 개수만큼 ArrayList를 선언

      - 자료형은 경우에 맞게 사용

 

 ✔ 가중치가 없는 그래프 표현

      - ArrayList<integer>[5]로 선언 *배열로 선언

      - 인접리스트에는 N번 노드와 연결되어 있는 노드를

        배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현

 

 ✔ 가중치가 있는 그래프 표현

      - Node를 생성해야 함

      - 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어나다