[자료구조] 그래프 개요

자료 구조 중 그래프에 대해 알아보자.
(기본 교과 과정에서 배웠던 수학의 그래프와는 전혀 관계 없음을 밝힌다)

그래프란?

: 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하는데 사용되는, 정점과 간선으로 구성된 데이터 구조이다.

• 정점(Vertex): 데이터를 표현 (사물, 개념 등).
  그래프의 기본 단위로, 각 정점은 고유한 값을 가질 수 있다. 정점은 일반적으로 원이나 점으로 표시된다.
• 간선(Edge): 정점간의 연결을 나타낸다. 간선은 방향이 있을 수도 있고, 없을 수도 있다. (일방향일 수도, 양방향일 수도 있다는 것).

ex) 소셜 네트워크 관계도, 지도와 길찾기, 웹 페이지 링크

아이돌 사진으로 보는 가상의 소셜 네트워크 관계도

위 예시에서 각 인물들이 정점(Vertex)가 될 것이고, 서로 친구 사이임을 표시하는 선이 간선이 될 것이다.
이 간선에 화살표를 주어 방향성을 표시할 수도 있을 것이고, 서로의 호감도 등 여러 정보를 담을 수도 있을 것이다.

그래프의 표현 방법

인접 행렬

• 정점 간의 간선을 2차원 배열로 나타낸다.
• 인접 행렬의 각 요소 [i][j]는 정점 i에서 정점 j로의 간선이 있는지를 나타낸다.

인접 리스트

• 각 정점에 연결된 다른 정점들을 리스트로 표현한다.
• 메모리를 효율적으로 사용할 수 있다.

그래프를 직접 구현해보는 포스트를 업로드 할 예정이니 참고하길 바란다.

  그래프가 중요한 이유는, 복잡한 관계를 시각화하고 분석하는 데 유용한 도구이기 때문이다. 무엇보다도 우리가 개발자로서 필수적으로 알아야 하는 최단 경로 알고리즘(ex: 다익스트라 알고리즘, A* 알고리즘), 네트워크 분석(소셜 네트워크 분석, 네트워크 플로우 문제 해결), 최적화 문제(최대 유량 문제, 최소 비용 문제 등) 등 다양한 분야에서 그래프 개념이 중요하게 활용되기 때문이다.