그래프란?
<aside>
🥕
연결 관계를 표현하는 자료구조
</aside>

트리는 그래프에 속하는 하위개념
-
트리 : 계층 관계를 표현하는 자료구조, 사이클 형성 X, 상하 관계(부모-자식 관계) 존재
-
그래프 : 보다 일반적인 연결 관계를 표현하는 자료구조, 사이클 형성 가능, 상하 관계 X
-
정점(데이터)를 간선(링크)로 연결한 형태의 자료구조
- 정점(Vertex) : 그래프의 노드. 객체 하나 하나를 의미
- 간선 or 링크(Edge) : 정점 간의 관계나 연결을 의미
그래프의 종류
- 그래프 = 연결관계를 표현하는 자료구조
- 즉, 간선이 중요한 역할을 담당(간선이 연결관계를 표현하는 것이기 때문)
- 간선이 어떠한 형태로 정점을 연결하느냐에 따라 그래프의 종류가 달라짐(대표적으로 아래 4가지)
- 무방향/방향 그래프
- 무가중치/가중치 그래프
- 연결/비연결 그래프
- 서브 그래프
1. 무방향/방향 그래프

무방향 그래프

방향 그래프
- 무방향 그래프 : 두 정점을 연결하는 간선에 방향이 없는 그래프
- 즉, 그냥 연결되어있다를 의미(무조건 양방향)
- 방향 그래프 : 두 정점을 연결하는 간선에 방향이 존재하는 그래프
- 즉, 간선이 가리키는 방향으로만 이동 가능(단방향 or 양방향)
2. 무가중치/가중치 그래프

무가중치 그래프

가중치 그래프
- 가중치 그래프 : 간선에 가중치가 부여된 그래프
- 비용 : 간선에 부여된 값인 가중치
- 즉, 연결되어있다고 해도 비용에 차이가 있음
- 무가중치 그래프 : 간선에 가중치가 부여되지 않은 그래프
3. 비연결/연결 그래프

G1 : 연결 그래프
G2 : 비연결 그래프(0에서 다른 정점으로 가는 경로가 없음)
G3 : 비연결 그래프(0에서 2로 가는 경로가 없음)
- 연결 그래프 : 임의의 두 정점 사이를 잇는 경로가 있는 그래프
- 아무 두 정점을 골라 경로를 확인했을 때, 경로가 있으면 연결 그래프
- 비연결 그래프 : 임의의 두 정점 사이를 잇는 경로가 없는 그래프
- 아무 두 정점을 골라 경로를 확인했을 때, 경로가 없으면 연결 그래프