[면접을 위한 CS 전공지식 노트][자료구조] Graph (그래프)

1. Graph

 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 네비게이션 길찾기, 네트워크 분석 등 다양하게 사용될 수 있다. 

 

2. Vertex와 Edge

 A라는 곳에서 무언가를 통해 B로 간다고 했을 때 A,B는 Vertex가 되고 A에서 B로 갈 때의 무언가는 Edge가 된다. Edge 같은 경우 단방향, 양방향 둘다 가능하다. 이 때 Vertex에서 나가는 Edge을 Outdegree라고 하고, Vertex로 들어오는 Edge을 Indegree라고 한다. 이때의 Vertex와 Edge들을 통합하여 그래프라고 부른다. 뿐만아니라 Edge별로 가중치를 다르게해서 Vertex들을 연결할 수 있다.

 

3. 정리

그래프는 Vertex와 그들을 연결해주는 Edge로 구성된다.  Vertex에서 나가는 Edge을 Outdegree, Vertex로 들어오는 Edge을 Indegree라고 한다. 

 

 

참조

면접을 위한 CS 전공지식 노트