<aside> ❓

그래프란, 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어진 자료구조

cf. 트리도 그래프의 한 종류이다.

</aside>

• 정점(Vertex) : 노드(node), 데이터 저장
• 간선(Edge) : 정점을 연결하는 선
• degree : 무방향 그래프에서 하나의 정점에 붙어있는 간선 개수
• in-degree : 방향 그래프에서 들어오는 간선의 수
• out-degree : 방향 그래프에서 나가는 간선의 수

그래프의 구현

1. 인접 행렬(Adjacency Matix) : 2차원 배열을 이용하여 연결 상태 값을 설정

   

   • 간선 정보 조회가 빠르지만 불필요한 메모리 공간을 차지한다.
   • 인접 행렬에서는 인접한 노드를 찾기 위해서 모든 노드를 전부 순회해야 한다.

2. 인접 리스트(Adjacency List) : 연결 리스트를 이용하여 모든 정점을 인접 리스트에 저장

   → ArrayList<Integer>[]을 만들어서 연결된 노드를 각각 저장

   

   • 간선 정보 확인이 오래 걸리지만 메모리 사용량이 상대적으로 적다.
   • 노드의 추가와 삭제가 빠르다.

⭐Graph in Programmers

프로그래머스에 있는 그래프 문제들

가장 먼 노드

순위

방의 개수