[코딩테스트/알고리즘] 그래프(Graph) - 그래프 종류, 그래프 용어

1. 그래프란

그래프는 자료구조의 일종으로 정점과 간선으로 나타낸다.

1. 정점(Vertex) : 노드(Node)라고도 불리며 데이터가 저장된다. 
2. 간선(Edge) : 정점 간의 관계를 나타낸다.

V개의 정점과 E개의 간선을 가진 그래프 G는

• G = (V, E)로 나타낸다.

---

2. 그래프의 종류

1) 방향이 있는 그래프

그래프의 간선 간에 방향이 있는 그래프

• A → C로 가는 간선은 있다.
• C → A로 가는 간선은 없다.

 

2) 방향이 없는 그래프 (양방향 그래프)

그래프의 간선 간에 방향이 없는 그래프

• A - C 간에 간선의 방향이 없다.
• A - C는 A → C 와 C → A를 나타낸다.

 

3) 간선이 여러개인 그래프(Mumtiple Edge)

두 정점 사이에 간선이 여러 개인 그래프

• 아래 그래프는 A - B를 연결하는 간선이 2개이다.
• 두 간선은 서로 다른 간선으로 취급한다.

4) 가중치(Weight)가 있는 그래프

간선 사이에 가중치가 있는 그래프

• A에서 B로 이동하는 거리
• A에서 B로 이동하는데 필요한 시간
• A에서 B로 이동하는데 필요한 비용
• 기타 등등

---

3. 그래프 용어

1) 경로(Path)

 한 정점에서 다른 정점까지 가는 간선의 조합

정점 A에서 B로 가는 경로

• A → C → D → E → B  
• A → B
• A → C → B
• A → C → D → B

 

2) 사이클(Cycle)

한 정점에서 다시 그 정점으로 돌아오는 경로

정점 A에서 B로 가는 경로

• A → C → B → A 
• A → C → E → D → B → A 
• A → C → D → B → A

 

3) 루프(Loop)

간선의 양 끝 점이 같은 경우

 

4) 차수(degree)

정점과 연결되어 있는 간선의 수

• 5의 차수 : 3
• 4의 차수 : 4

 

방향 그래프의 경우 In-deree, Out-degree로 나누어서 차수를 계산한다.

• In-degree : 들어오는 간선의 수
• Out-degree : 나가는 간선의 수 

• 4의  In-degree : 3
• 4의  Out-degree : 1

---

총평

 그냥 힘들다.