비선형 자료구조 2 (그래프)

안녕하세요

 

게임개발자가 되기위해 공부하고 있는 구구입니다.

오늘은 비선형 자료구조의 그래프에대해 알아보도록 하겠습니다.

---

• 그래프

- G = (V, E)

- 정점 : 노드

- 간선 : 정점끼리 연결한 선

 

 

• 그래프의 특징

- 트리와 달리 사이클을 돌 수 있음

 

 

• 그래프의 종류

1. 방향 그래프 : 간선에 화살표가 있는 경우(방향이 있는 경우)

 

 

 

2.무방향 그래프 : 간선에 화살표가 없는 경우(양쪽으로 이동 가능)

 

 

 

3.순환 그래프(사이클이 있는 그래프)

 

 

4.비순환 그래프(사이클이 없는 그래프)

 

 

 

5. 가중치 그래프(보통 경유지 구현시 자주 사용)

 

 

 

 

• 그래프의 표현 - 인접 리스트

 

- 제일 앞이 그래프에 존재하는 노드

- 그 뒤로 연결된 것은 제일 앞의 노드와 연결된 정점들

 

 

• 그래프의 표현 - 행렬