💡Graph

---

📌Graph 개념

• 여러 개의 점들이 서로 복잡하게 연결되어 있는 연결 데이터를 저장할 수 있는 자료구조
• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선으로 연결되며, 간접적인 관계가 있는 경우 몇 개의 점과 선을 통해 연결된다.
• 그래프에서는 하나의 점을 정점(Vertex/node)라고 표현하고, 하나의 선을 간선(edge)라고 표현한다.
• 주로 네이게이션, 사회연결망(SNS), 포털사이트 검색엔진에서 주로 사용한다.

📌Graph 용어

정점(node)

• 그래프에서 하나의 데이터 단위를 나타내는 객체

간선(edge)

• 그래프에서 두 정점의 직접적인 연결 관계 데이터

인접

• 두 정점 간에 간선이 직접 이어져 있는 것을 '인접'이라고 표현한다.

경로

• 한 정점에서 다른 정점까지 가는 길로 즉, 정점들을 잇는 간선들을 '경로'라고 한다.
• 무가중치 그래프(=비가중치 그래프)에서 경로의 거리는 간선의 수로 표현하지만, 가중치 그래프에서 경로의 거리는 한 경로에 있는 간선의
  가중치의 합으로 표현한다.
• 두 정점 사이의 가장 짧은 경로를 '최단 경로'라고 표현한다.

가중치 그래프

• 무가중치 그래프(=비가중치 그래프)의 경우 거리는 단순하게 경로에 있는 간선 수를 의미
• 가중치 그래프의 경우 거리는 경로 내에 있는 모든 간선의 가중치들의 합을 의미

사이클

• 한 정점에서 출발하여 다시 해당 정점에서 끝나는 경로를 '사이클'이라고 표현

차수

• 한 정점이 가지고 있는 간선의 수를 '차수'라고 표현
• 진입차수(in-degree)와 진출사추(out-degree)로 나눌 수 있다.

무방향 그래프

• 무방향 그래프의 예시로는 친구관계가 있다.
• 정점을 잇는 간선을 화살표가 없는 직선으로 표현
• 그래프의 특정 경로를 읽을 때에도 정점의 순서 상관없이 읽으면 된다.

방향 그래프

• 방향 그래프의 예시로는 SNS 팔로우가 있다.
• 정점을 잇는 간선을 화살표가 있는 직선으료 표현
• 방향 그래프에서는 간선이 떠나는 정점의 순서를 앞에, 간선이 들어가는 정점의 순서를 뒤로 하여 읽으면 된다.
• 방향이 있다해도 쌍방향 가능(순방향과 역방향인 간선들을 만들면 된다)

📌 무방향 그래프와 방향 그래프의 차이점

1. 경로
   : 방향 그래프에서는 경로에도 방향이 있다.
2. 간선의 차수
   : 방향 그래프에서는 차수를 출력 차수와 입력 차수, 2개로 나눈다.