그래프 자료구조와 구현 방법
그래프 자료구조는 정점(Vertex)과 이들을 연결하는 간선(Edge)으로 구성된다. 이는 연결된 객체 간의 관계를 모델링하는 데 사용된다. 그래프는 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 크게 분류된다. 또한, 사이클을 포함할 수 있으며, 사이클이 없는 그래프는 비순환 그래프(Acyclic Graph)라고 한다. 그래프는 주로 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix) 두 가지 방법으로 구현된다.
인접 리스트(Adjacency List)
인접 리스트는 각 정점별 인접 정점 리스트를 배열이나 링크드 리스트로 저장한다. 배열의 각 인덱스는 그래프의 정점을 나타내고, 각 인덱스에 저장된 리스트는 해당 정점에 인접한 정점들을 나타낸다.
- 두 정점이 연결되었는지 확인하는 시간복잡도: (O(V)), 여기서 (V)는 정점에 연결된 간선의 수이다.
- 한 정점에 연결된 모든 정점을 찾는 시간복잡도: (O(1))로 시작하지만, 모든 인접한 정점을 순회하는 데 (O(V))의 시간이 소요된다.
- 공간복잡도: (O(V+E)), 여기서 (V)는 정점의 수, (E)는 간선의 수이다.
인접 행렬(Adjacency Matrix)
인접 행렬은 2차원 배열을 사용해 정점들 사이의 연결 관계를 나타낸다. 배열의 각 행과 열은 그래프의 정점을 나타내며, 배열의 각 요소는 두 정점 사이의 간선의 유무(또는 가중치)를 나타낸다.
- 두 정점이 연결되었는지 확인하는 시간복잡도: (O(1)), 두 정점 사이의 관계를 배열에서 직접 조회할 수 있기 때문이다.
- 한 정점에 연결된 모든 정점을 찾는 시간복잡도: (O(V)), 해당 정점과 연결된 모든 정점을 찾기 위해 행 또는 열을 전체 순회해야 한다.
- 공간복잡도: (O(V^2)), 정점의 수에 따라 2차원 배열의 크기가 결정된다.
정점의 개수 (N), 간선의 개수 (N^3)일 때의 효율적인 구현 방식
정점의 개수에 비해 간선의 개수가 매우 많다는 것은 각 정점이 거의 모든 다른 정점과 연결되어 있음을 의미한다. 이런 상황에서는 인접 리스트가 인접 행렬에 비해 공간 측면에서 훨씬 더 효율적이다. 간선의 수가 (N^3)이라면, 공간 복잡도는 (O(N+N^3))이 되며, 실제 메모리 사용량은 간선의 수가 지배적이므로 (O(N^3))으로 간주할 수 있다.
사이클이 없는 그래프와 트리
사이클이 없는 그래프는 모든 트리가 비순환 그래프이지만, 모든 비순환 그래프가 트리는 아니다. 트리는 특별한 종류의 그래프로서, 다음과 같은 특성을 가진다:
- 모든 정점이 연결되어 있어야 한다(연결 그래프).
- 정확히 (V-1)개의 간선을 가져야 한다.
- 사이클을 포함하지 않는다.
비순환 그래프가 트리가 되려면, 모든 정점이 서로 연결되어 있어야 한다. 하나 이상의 정점이 나머지 그래프와 연결되지 않은 경우, 그 그래프는 숲(Forest)으로 간주된다. 숲은 하나 이상의 분리된 트리로 구성된 비순환 그래프이다.
예시: 세 개의 정점 (A, B, C)가 있고, A와 B만 연결되어 있으며, C는 연결되어 있지 않다. 이 그래프는 사이클이 없지만 모든 정점이 연결되어 있지 않으므로 트리가 아니다. 이는 연결되지 않은 비순환 그래프의 한 예로, 트리의 정의를 만족하지 않는다.
