그래프(Graph) 자료구조

그래프

 

- Vertex, edge로 구성된 자료구조

- Vertex == Node

그래프 Graph

- 네비게이션 길찾기

- 게임 내 캐릭터 이동

- 지식 그래프

 

 

쾨니히스베르크의 다리 문제

- 한 다리를 두번 이상 건너지 않고 모든 다리를 건널 수 있나? -> 불가능함

 

 

방향 그래프 Directed Graph

 

가중치 그래프

 

루프 loop

순환 그래프 Cyclic Graph

 

 

그래프의 구현

 

- 인접 행렬

- 2차원 배열로 구현

단점은 메모리를 많이 써야한다,

새로운 노드 생기면 연산량이 늘어난다.

 

인접 리스트

- Vertex 갯수 만큼의 list 사용

효율적인 메모리 공간

생성 추가 수월함

인접행렬보다 edge를 찾는데 오래 걸릴 수 있음

 

 

그래프 순회

- 그래프 탐색 

- 위상 정렬

- 그래프의 최단거리

 

DFS

- 깊이 우선 탐색

 

BFS

- 너비 우선 탐색

 

 

---