[자료구조] 그래프(Graph)
- 그래프 정의
- 용어 정리
- 그래프 종류
- 그래프 VS 트리
그래프란?
: 데이터 간의 관계를 점과 선으로 나타낸 자료구조
용어정리
정점 (Vertex) : 위치 (= node)
간선 (Edge) : 두 정점을 연결한 선, 관계 (= link, branch)
차수 : 정점에 연결된 edge 수
진입 차수 : 방향 그래프에서 정점으로 들어오는 edge 수
진출 차수 : 방향 그래프에서 정점에서 나가는 edge 수
경로 : 연결된 정점을 나열한 것
단순경로 : 중복된 정점이 없는 경로
경로 길이 : 경로에 쓰인 edge 수
사이클 : 시작과 끝 정점이 같은 경로
그래프 종류
그래프를 G=(V,E)와 같이 표기 ( V : 정점의 집합, E : edge의 집합 )
1. 무방향 그래프
: edge에 방향(화살표)가 없는 그래프
(A, B) : 방향이 없어서 (B, A)와 동일
2. 방향 그래프
: edge에 방향이 있는 그래프
<A, B> : A -> B
3. 가중 그래프
: edge에 비용 또는 가중치가 할당된 그래프
4. 완전 그래프
: 모든 정점이 edge로 연결돼있는 그래프
5. 부분 그래프
: 원래 그래프에서 정점이나 edge를 일부만 제외하여 만든 그래프
6. 연결 그래프 / 단절 그래프
연결 : 모든 정점에 경로가 있는 그래프
단절 : 특정 정점에 경로가 없는 그래프
그래프 VS 트리
