Graph

Graph(그래프)

그래프는 객체들 간의 관계를 표현하는 추상적인 자료 구조이다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성되며, 정점은 개별적인 객체를 나타내고, 간선은 정점들 간의 관계를 나타낸다.

그래프의 관계 표현

그래프는 다양한 형태의 관계를 표현할 수 있다. 일반적으로 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 구분된다.

1. 무방향 그래프 :
   • 간선에 방향이 없는 그래프, 간선을 통해 두 정점이 양방향으로 연결된다.
   • 예를 들어, 친구 관계 네트워크를 모델링할 때 사용할 수 있다.
2. 방향 그래프 :
   • 간선에 방향이 있는 그래프, 간선은 한 정점에서 다른 정점으로의 방향을 가지며, 단방향으로 연결된다.
   • 예를 들어, 도로 네트워크를 모델링할 때 사용할 수 있다.

그래프의 구현 방식

그래프는 다양한 방식으로 구현 가능하다. 대표적인 구현 방식으로는 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)이 있다.

1. 인접 리스트 :
   • 그래프의 각 정점마다 해당 정점과 인접한 정점들은 연결 리스트 형태로 저장
     • 이 방식은 그래프의 크기에 비해 적은 메모리를 사용
     • 정점간의 연결 여부를 효율적으로 확인 가능
     • 하지만 특정 정점의 인접 여부 확인을 위해 리스트 탐색하는 비용 발생
2. 인접 행렬:
   • 그래프의 정점들은 2차원 배열로 표현하며, 정점 간의 여부를 행렬의 원소로 표현하며, 연결된 경우 1 또는 가중치 값을 저장
     • 이 방식은 특정 정점의 인접 여부를 상수 시간에 확인 가능
     • 하지만 그래프가 밀집되지 않은 경우 많은 메모리 공간이 낭비되는 상황 발생

그래프 활용

그래프는 네트워크, 지도, 소셜 네트워크, 의존성 관리 등 다양한 분야에서 활용된다. 그래프 알고리즘은 최단 경로 찾기, 신장 트리 구성, 너비 우선 탐색, 깊이 우선 탐색 등 다양한 그래프 분석과 탐색에 활용된다.