[게임 프로그래머 입문 올인원] 비선형 자료구조 3 : 그래프 기초 (57강)

C. 비선형 자료구조

4. 그래프 기초

트리랑 유사하지만 범위가 더 넓다

(트리가 그래프의 일종)

 

a. 그래프의 개념

🌟 현실 세계의 사물이나 추상적인 개념간의 연결관계를 표현

 

• 정점(Vertex) : 데이터를 표현 (사물, 개념 등)
• 간선(Edge) : 정점들을 연결하는데 사용

 

대표적으로 소셜 네트워크

👉 내용은 어렵지 않지만 내용을 분석하는게 중요함

b.그래프 종류

간선에 추가적인 정보를 넣어서 그래프의 종류를 표현할 수 있음

 

• 가중치 그래프 : 지하철 노선도
• 방향 그래프 : 도로망(일방 통행 포함), 사랑의 짝짓기

 

 

💙 게임에서 그래프를 이용해야 하는 상황

* 길찾기
* 서버에서 락을걸어 멀티스레드를 관리할 때 데드락 체크
* 도로망
* 가족관계도 등

👉 즉, 이론을 알면 구현할 수 있는게 너무 많기 때문에 꼭 공부해야 함

 

c. 그래프 구현하기

👉 그래프를 Vertex 구조체로만 만들지 않는 이유

그래프는 Vertex 구조체가 아쉽다

 

1) 인접리스트로 구현하기

 

이걸 구현할 예정

 

인접 리스트를 만들어 실제 연결된 애들만 넣어줌

이중벡터를 사용하는 adjacent로 연결여부를 따로 관리해줌 

 

push_back이랑 바로 그 아래 코드{}랑 동일

 

2) 인접 행렬

 

맨 아래줄은 행렬 초기화

 

연결되어있는지 확인하는것은 adjacent 함수로 t/f 관리가능
메모리 소모 심하지만 빠른 접근이 가능 

 

 

 

d. 인접리스트 vs 인접행렬

인접 행렬 : 행렬을 이용한 그래프 표현 (연결된 목록을 행렬로 관리)

 

• 데이터가 많으면 인접행렬 (친구목록)
• 적다면 인접리스트 (지하철)

 

e. 간선의 표현

이중벡터로 연결된 부분만 저장해둔다 (연결이 안되어있다면 -1)

 

👉 위와같이 adjacent라는 인접 정보를 따로 관리하는게 중요함

d. 데이터 순회하기

데이터는(벡터, 리스트, 큐, 트리 등) 모두 전체순회를 하는게 중요함
하지만 트리는 기준을 잡기 어려워서 데이터를 순회하는것 조차 어려움

두가지 방법 (BFS, DFS) 으로 스캔할 수 있는데 
그 부분에서 많은 정보를 수집할 수 있음 

다음에 계속....

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -

사진 출처 : https://velog.io/@taste1729/Graph

Graph