그래프 G(Graph)는 노드 V(Vertex 정점 혹은 Node)와 간선 E(Edge)의 집합으로 정의됨
노드는 일반적으로 모델링하려는 시스템을 구성하는 객체를 나타내며, 간선은 이러한 객체 사이의 관계를 정의함
G = (V(G), E(G)) = (V,E)
위 식은 그래프 G는 노드들의 집합 V(G)와 간선들의 집합 E(G)로 구성된다는 의미임
그래프와 관련된 기본적인 용어로는 인접, 부속, 차수, 경로 등이 있다.
- 인접
두 개의 노드를 연결하는 간선이 존재할 때 두 노드는 인접(Adjacent)되었다고 한다.
- 부속
두 개의 노드를 연결하는 간선이 존재할 때 이 간선은 두 노드에 각각 부속(Incident)되었다고 한다.
- 차수
노드에 부속된(연결된) 간선의 개수를 차수(Degree)라 한다.
- 경로
두 노드 A에서 노드 B까지의 경로(Path)는 노드 A에서 노드 B에 이르는 간선들의 인접(Adjacent) 노드를 순서대로 나열한 리스트를 말한다.
- 루프
그래프의 임의의 노드에서 자기 자신으로 이어지는 간선을 루프(Loop)라고 한다.
그래프를 구현하는 방법에는 인접 행렬(Adjacency Matrix)을 이용하는 방법과 인접 리스트(Adjacency List)로 구현하는 방법 등이 있다. 두 가지 방법 모두 그래프의 각 노드별로 인접한 노드를 저장한다.
먼저 인접행렬을 이용해 그래프를 구현하는 방법을 알아보자
행렬 GA가 있을 때, GA[i][j]에 들어가는 값은 1 또는 0이며 노드 i와 j 사이에 간선이 있으면 1이 들어가고 없으면 0이 들어간다. (이때, 방향성이 없는 무방향그래프라면 GA[i][j]=GA[j][i] )
이때 가중치가 있는 방향그래프라면 GA[i][j]에는 1이 아니라 해당하는 간선의 가중치가 들어간다.
행렬에서 행을 From이라고 생각하고 열을 To라고 생각하면 GA[0][1]은 노드0에서 나가 노드1로 들어가는 간선을 의미한다.
다음은 인접 리스트를 이용해 그래프를 구현하는 방법을 알아보자
그래프를 인접 리스트로 구현하는 방법은 정점별 인접 정점을 연결 리스트(Linked List)로 저장하는 방식이다. 즉 인접 행렬에서는 간선 저장을 통해 그래프를 나타내었다면, 인접 리스트는 특정 노드에 연결되는 노드를 저장하는 방식을 통해 그래프를 구현한다.
연결 리스트를 이용하여 노드별 인접 노드를 저장하는 방식은 메모리를 절약할 수 있다. 인접 행렬이 노드 사이의 연결 여부와 상관 없이 모든 간선의 정보를 2차원 배열에 저장한 반면, 인접 리스트는 실제 연결된 노드만을 저장한다. 따라서 연결되지 않는 노드 사이의 연결 정보를 저장하지 않기 때문에 불필요한 메모리 낭비를 절약할 수 있다.
단, 인접 리스트는 구현의 복잡성이 증가한다는 단점과 저장하는 그래프가 희소 그래프(그래프의 대부분의 값이 0)가 아닌 경우에는 오히려 인접 행렬보다 메모리 효율성이 떨어지는 특성을 지니고 있다. 인접 리스트는 포인터까지 저장해야하기 때문이다. 또, 저장한 간선에 접근하는 시간도 인접 행렬보다 인접 리스트가 더 오래 걸린다. 인접 행렬에서 특정 간선에 대한 접근이 O(1)의 시간 복잡도를 가진다면, 인접 리스트에서는 평균 O(n)의 시간 복잡도를 가진다. 즉 특정 시작 노드에 대한 인접 리스트까지의 접근은 O(1)로 가능하지만, 해당 연결 리스트에서 종료 노드를 찾기 위해 연결 리스트를 순회하는 연산은 평균 O(n)의 시간 복잡도가 소요된다.
정리)
메모리 낭비가 심한 희소 그래프의 경우면 인접 리스트를 사용
간선 정보에 대한 빠른 접근이 필요하다면 인접 행렬을 사용