그래프

 

*그래프의 개념

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

 

정점(Vertex): 데이터를 표현 (사물, 개념 등)

간선(Edge): 정점들을 연결하는데 사용

 

*가중치 그래프

간선에 가중치를 끼워 넣음 (가중치는 거리, 비용 등의 관계를 표현 할 수 있음)

 

*방향 그래프

정점간 간선의 방향을 표현  (반대의 경우 방향이 없는 그래프)

 

*그래프의 표현

C#에선 그래프와 관련된 클래스를 제공하고 있지 않으므로, 코드로 직접 그래프를 구현해야함.

 

(1)예를 들어 그래프의 정점을 구현하는 인스턴스를 생성하거나 int 리스트의 배열을 이용 - 메모리 소모가 상대적으로 덜하다. 접근이 느리다.

(2)행렬(2차원 배열)을 이용 - 메모리 소모가 (1)보다 크다. 접근이 빠르다.

 

*그래프의 탐색

가장 많이 보이는게 깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Bredth First Search) 그 외 등등 여러가지 알고리즘이 있다.