27장 그래프의 표현과 정의

27.1 도입

# 그래프의 정의

그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조이다. 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다.

 

# 그래프의 종류

방향 그래프(directed graph, 유향 그래프): 방향 그래프에서는 각 간선이 방향이라는 새로운 속성을 갖는다. 방향 그래프에서 두 정점 u, v가 있을 때 u에서 v로 가는 간선과 v에서 u로 가는 간선은 서로 다른 간선이다.

무방향 그래프(undirected graph): 간선에 방향이 없는 그래프.

가중치 그래프(weighted graph): 가중치 그래프는 각 간선에 가중치(weight) 속성을 부여한다. 이 속성은 두 도시 사이의 거리, 두 물건 사이의 교환 비율 등을 표현하는데 사용한다.

그래프의 형태로 그래프를 분류하는 경우도 있다.

다중 그래프(multigraph): 두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프.

트리 혹은 루트 없는 트리(unrooted tree): 부모 자식 관계가 없고 간선들의 연결 관계가 트리와 같은 무향 그래프.

이분 그래프(bipartite graph): 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록 만들 수 있는 그래프.

사이클 없는 방향 그래프(directed acyclic graph, DAG): 한 정점에서 출발해 자기 자신으로 돌아오는 경로(사이클)가 존재하지 않는 방향 그래프.

 

# 그래프의 경로

경로란 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것이다. 경로 중 한 정점을 최대 한 번만 지나는 경로를 단순 경로(simple path)라고 한다. 시작한 점에서 끝나는 경로를 사이클(cycle)이라 한다.

27.2 그래프의 사용 예

# 철도망의 안정성 분석, 절단점 찾기 알고리즘

# 소셜 네트워크 분석, 너비 우선 탐색(BFS)

# 인터넷 전송 속도 계산, 최소 스패닝 트리 알고리즘

# 한 붓 그리기, 오일러 경로(Eulerian path), 깊이 우선 탐색(DFS)

# 외환 거래, 아비트러지(arbitrage), 최단 거리 알고리즘

27.3 암시적 그래프 구조들

# 할 일 목록 정리, 위상 정렬(topological sorting)

# 15-퍼즐, 최단 경로 문제

# 게임판 덮기, 이분 매칭 알고리즘

# 회의실 배정, 만족성 문제(satisfiability problem), 2-SAT

27.4 그래프의 표현 방법

#인접 리스트 표현

인접 리스트(adjacency list) 표현은 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프를 표현한다. 따라서 그래프는 각 정점마다 하나의 연결 리스트를 갖는 방식으로 구현한다. 예를 들어 다음과 같다.

vector<list<int>> adjacent;

// 다음과 같이도 쓸 수 있다. V는 정점의 개수.
vector<int> adjacent[V];

만약 가중치 그래프 등 간선이 추가적 속성을 갖는 그래프라면, 간선의 정보를 구조체로 표현한다. 예를 들어 다음과 같다.

struct Edge {
	int vertex;		// 간선의 반대쪽 끝 점의 번호
    int weight;		// 간선의 가중치
};

 

#인접 행렬 표현

인접 행렬(adjacency matrix) 표현은 2차원 배열을 이용해 그래프의 간선 정보를 저장한다. 형태는 다음과 같다.

vector<vector<bool>> adjacent;

// 또는 2차원 배열 표현. V는 정점의 개수.
bool adjacent[V][V]

만약 가중치 그래프를 인접 행렬로 표현하려면 간선 정보를 bool 대신 int나 double 변수로 둔다. 두 정점 사이에 간선이 없는 경우에는 이 값을 -1 혹은 아주 큰 값 등 존재할 수 없는 값으로 지정하면 된다.

 

#인접 행렬 표현과 인접 리스트 표현의 비교

인접 행렬 표현의 장점은 정점의 번호 u, v가 주어졌을 때 두 정점을 잇는 간선의 유무를 \(O(1)\)에 확인할 수 있다. 반면 인접 리스트 표현의 경우, 간선 (u, v)가 존재하는지 확인하기 위해서는 연결 리스트 adjacent[u]의 각 원소를 확인해야 한다. 메모리 측면에서 인접 행렬 표현은 \(|V|\times|V|\) 크기의 2차원 배열을 사용하기 때문에 간선의 개수와 관계없이 항상 \(O(|V|^2)\)크기의 공간을 사용한다. 인접 리스트 표현은 \(|V|\)개의 연결 리스트에 실제 간선 수만큼의 원소가 들어있으므로, \(O(|V|+|E|)\)의 공간만을 사용한다. 간선의 수가 \(|V|^2\)에 비해 훨씬 적은 그래프를 희소 그래프(sparse graph)라고 한다. 반대로 간선의 수가 거의 \(|V|^2\)에 비례하는 그래프를 밀집 그래프(dense graph)라고 한다. 따라서 희소 그래프에 대해서는 인접 리스트를, 밀집 그래프에 대해서는 인접 행렬을 사용하는 것이 유리하다.