그래프 이론

그래프 이론

그래프 이론은 객체 간에 연결된 관계를 모델링하기 위해 사용되는 수학 구조인 그래프를 연결하는 수학, 컴퓨터과학의 한 분야이다.

그래프는 그래프 이론에서 다루는 수학적 대상이다. 그래프는 정점(또는 꼭짓점)과, 두 정점을 연결하는 변(또는 모서리)들로 구성된다.

일반적으로 정점은 점으로 표현하고 변은 선분으로 표현한다. 변에 방향을 부여한 그래프를 방향 그래프 라고 하며, 이 경우 변을 화살표로 표현한다.

위 그림의 그래프에서는 2,3,4,5번 정점들이 서로 연결되어 하나의 순환을 이룬다. 다시 말해서 2번 정점에서 출발하여 3,4,5번 정점을 순서대로 하나씩만 거친 후 다시 2번에 도착할 수 있는데, 이러한 구조를 순환 또는 사이클이라고 한다.

한편 이렇게 순환을 가지지 않는 연결된 그래프를 트리라고 한다.

그래프의 종류

그래프의 종류는 특징의 존재 여부에 따라 여러가지 그래프로 불린다.

(1) 방향성 여부

• 무방향 그래프 (Undirected): 간선이 양방향 (A->B는 B->A와 같음)
• 방향 그래프 (Directed, Digraph): 간선이 한 방향만 (A->B ≠ B->A)

(2) 가중치 여부

• 가중치 그래프 (Weighted): 간선에 비용, 거리, 시간 같은 값이 있음
• 비가중치 그래프 (Unweighted): 모든 간선의 가중치 동일 (보통 1로 취급)

(3) 특수 형태

• 트리(Tree): 사이클이 없고, N−1N-1N−1개의 간선을 가진 연결 그래프
• 완전 그래프 (Complete Graph): 모든 정점이 서로 연결
• 이분 그래프 (Bipartite Graph): 정점을 두 그룹으로 나눠서 같은 그룹 내에서는 연결 없음

그래프 구현 방법

그래프를 구현하는 방법은 여러가지가 있다.

1. 인접 행렬

2차원 배열로 간선의 존재 여부를 저장하는 방식

ex) 1번 노드에서 2번노드의 간선은

int graph[n][m];
graph[1][2] = k;

와 같은 식으로 저장한다.

• 장점
  • 간선 존재 여부 확인 = O(1)
  • 구현이 직관적임
• 단점
  • 메모리 사용량 = O(n^2)
  • 간선 개수가 적으면 메모리가 낭비됨

2. 인접 리스트

각 정점에 연결된 노드들을 리스트로 저장하는 방식

vector<int> graph[5]; // 그래프 정의
graph[1].push_back(2); // 1번 노드에서 2번 노드로의 간선 표현

• 장점
  • 메모리 사용량 = O(N+E)
• 단점
  • 간선 존재 여부 확인 = O(정점 차수)
  • 정점이 연결된 노드를 찾기 위해 순회가 필요함

3. 간선 리스트

간선만 따로 저장하는 방식

vector<pair<int,int>> edges;
edges.push_back({1,2}); // 1번과 2번 사이의 간선 저장

• 장점
  • 구현이 단순함
  • 간선 정렬, 필터링에 유리함
• 단점
  • 특정 간선 존재여부 확인 = O(E)
  • 인접 노드를 찾으려면 전체 탐색이 필요함

간선에 가중치가 있을 경우

1. 인접 행렬 : k에 가중치 저장
2. 인접 리스트 : pair를 사용하여 인접 노드의 번호와 그 가중치를 함께 저장
3. 간선 리스트 : tuple 자료구조를 사용하여 두 노드의 번호와 그 가중치를 함께 저장