그래프

• 정점과 간선으로 이루어진 자료구조

Graph의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다.

Graph 용어

• 정점(vertex) - 하나의 점(노드라고도 한다)
• 간선(edge) - 하나의 선(정점 간의 관계를 나타냄)
• 인접 (adjacency) : 두 정점 간에 간선이 직접 이어져있다면 인접하다고 표현한다.
• 인접 정점 (adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 : 간선과 정점 사이에 드는 비용
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
• 무(방)향 그래프, 단방향 그래프
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
• 자기 루프 (self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 → 다른 정점을 거치지 않는다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다
  고 표현
• 정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 정점의 indegree라고 한다.

표현 방식

인접행렬

• 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 표현
• 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬(2차원배열)
  • 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용

인접 리스트

• 각 정점이 어떤 정점과 인접하는지를 나타낸 리스트
• 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고있다.
• 메모리를 효율적으로 사용하고 싶을 때 주로사용
  • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지

실사용 예제

• 포털 사이트의 검색 엔진
• SNS에서 사람들과의 관계
• 내비게이션 (길 찾기)
  • 간선은 내비게이션에서 이동할 수 있음을 나타냄
  • 서로 이어져 있다는 사실만 알려줄뿐 거리가 얼마나 되는지는 알려주지 않는다.
• 추가적인 정보를 파악할수없는 그래프, 가중치(연결의 강도가 얼마나되는지) 적혀 있지 않은 그래프를 비가중치 그래프라고 한다.
• 선에 연결 정도(거리 등)를 표현한 그래프를 가중치 그래프라고 한다.
  

Map

• 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조
• 레드 블랙 트리 자료구조를 기반으로 형성되고, 삽입하면 자동으로 정렬된다.
• 해시 테이블을 구현할때 쓰인다.

Set

• 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
• 중복 요소는 없고 오로지 unique 값만 저장하는 자료구조