c로 쓴 자료구조론 연습문제 6장(그래프)

1. 그래프의 기본 개념

그래프는 서로 연결된 객체들의 집합으로 정의된다. 그래프의 기본 구성 요소는 정점(vertex)과 간선(edge)이다. 정점은 그래프 내의 개별 데이터를 의미하며, 각각의 정점은 유일한 식별자를 갖는다. 간선은 두 정점 사이의 연결을 나타내며, 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다. 방향 그래프에서는 간선이 일정한 방향성을 가지며, 이는 예를 들어 도로망 내의 일방통행 도로나 정보 흐름 그래프 등에 적용된다. 무방향 그래프는 간선이 양방향을 허용하는 구조로, 지하철 노선이나 소셜 네트워크 내의 친구 관계처럼 쌍방향 연결을 나타내는 데 적합하다. 그래프는 다양한 분야에서 활용되며, 2020년 통계에 따르면 네트워크 분석 시장은 전 세계적으로 약 25억 달러의 규모를 기록했다. 이는 기업들이 고객이나 공급망 네트워크의 구조를 분석하는 데 그래프를 활용하는 사례가 급증했음을 보여준다. 그래프는 인접 행렬과 인접 리스트라는 두 가지 대표적인 저장 방식이 있다. 인접 행렬은 정점 수가 적은 경우 적합하며, 메모리 사용량이 정사각형 크기인 O(n^2)로 증가한다. 반면, 인접 리스트는 정점의 연결 관계만…