그래프란
- 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현
- 정점(Vertex_아이템)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조
- 선형구조(1:1)나 트리자료구조(1:N)로 표현하기 어려운 M:N 관계를 표현
* 정점: A, B, C, D
* 간선: 선분들
* 차수: A, B, C, D의 차수는 모두 3으로 동일
* 두 정점 사이에 간선이 존재하면 '인접하다'라고 표현그래프의 유형
무향 그래프(Undirected Graph)와 유향 그래프(Directed Graph)
- 무향 그래프 : 왕복(양방향 연결 가능)
- 유향 그래프 : 편도
가중치 그래프
보통은 간선의 가중치를 1이라고 여긴다. 다만 아래와 같이 각 간선에 값을 매겨서 가중치를 부여할 수 있다.
순환 그래프
M:N의 관계를 표현할 수 있다.
사이클 없는 방향 그래프(DAG, Directed Acyclic Graph)
완전 그래프
정점들에 대해 가능한 모든 간선들을 가진 그래프
간선의 개수 = V * (V-1) / 2
부분 그래프
원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
트리는 그래프일까?
트리는 그래프이다. ⭕
그래프는 트리이다. ❌
그래프 ⊃ 트리 ⭕
