[자료구조] 그래프(Graph)

• 그래프 정의
• 용어 정리
• 그래프 종류
• 그래프 VS 트리

---

 

그래프란?

: 데이터 간의 관계를 점과 선으로 나타낸 자료구조

출처 : https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

---

 

용어정리

정점 (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에 비용 또는 가중치가 할당된 그래프 

가중 or 가중치 그래프

 

4. 완전 그래프

: 모든 정점이 edge로 연결돼있는 그래프 

완전 그래프

 

5. 부분 그래프

: 원래 그래프에서 정점이나 edge를 일부만 제외하여 만든 그래프

부분 그래프

 

6. 연결 그래프 / 단절 그래프

연결 : 모든 정점에 경로가 있는 그래프

단절 : 특정 정점에 경로가 없는 그래프

연결 그래프, 단절 그래프

---

그래프 VS 트리

출처 :&nbsp;https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

 

참고 : https://foxtrotin.tistory.com/209