그래프
'그래프' 그래프는 정점(Vertex)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료 구조로 각 정점이 간선을 통해 연결되어 있으면 이를 '인접했다(adjacent)'고 표현한다. 일반적으로 그래프(G)는 G=(V, E)로 표현되는데 V는 정점의 집합, E는 간선들의 집합을 의미한다.
그래프의 종류
무방향 그래프(Undirected graph)
두 정점을 연결하는 간선에 어떤 방향성이 존재하지 않는 그래프이다. 무방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 (Vi, Vj)로 표현하는데, 무방향 그래프에서는 (Vi, Vj)와 (Vj, Vi)가 같은 간선임을 나타낸다.
방향 그래프(Directed graph)
간선에 방향이 존재하는 그래프로, 이때는 정점 Vi와 Vj를 연결하는 간선을 <Vi, Vj>와 같이 표현하며 여기서 Vi를 꼬리(tail), Vj를 머리(head)라고 한다. 방향이 존재하기 때문에 <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선이다.
완전 그래프(Complete graph)
완전 그래프는 한 정점에서 다른 모든 정점과 연결되어 최대의 간선 수를 갖는 그래프이다. 방향성과는 별개의 개념으로, 정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수는 n(n-1)/2개이고 방향 그래프의 최대 간선 수는 n(n-1)개이다.
부분 그래프(Subgraph)
부분 그래프는 기존의 그래프에서 일부 정점 혹은 간선을 제외하여 만든 그래프를 말한다.
가중 그래프(Weighted graph)
정점을 연결하는 간선에 가중치가 할당된 그래프이다.
기타 그래프
- 유향 비순환 그래프(Directed Acyclic Graph, DAG) : 방향 그래프에서 사이클이 없는 그래프
- 연결 그래프(Connected graph) : 떨어져 있는 정점이 없는 그래프
- 단절 그래프(Disconnected graph) : 연결되지 않은 정점이 있는 그래프
그래프 관련 용어
- 정점(Vertex) : 노드(Node)라고도 하며, 데이터가 저장되는 그래프의 기본 원소
- 간선(Edge) : 링크(Link)라고도 하며, 정점 간의 연결 관계
- 인접 정점 : 간선에 의해 연결된 정점
- 차수 : 간선을 따라 이동할 수 있는 정점으로, 정점을 나열하여 표시
- 경로의 길이 : 경로를 구성하는 데 사용되는 간선의 개수
- 단순 경로 : 경로 중 반복되는 정점이 없는 경우
- 사이클 : 시작 정점과 종료 정점이 같은 단순 경로
그래프의 구현
파이썬에서는 그래프를 구현할 때 인접 행렬 혹은 인접 리스트의 형태로 구현할 수 있다.
인접 행렬을 이용한 구현
인접 행렬은 NXN 행렬로서 matrix[i][j]=1이면 정점 i에서 j로 가는 간선이 존재하고 matrix[i][j]=0이면 간선이 존재하지 않는다는 의미이다. 이때, 가중 그래프의 경우 해당 가중치 값을 입력하며, matrix[i][j]>0이면 i에서 j로 가는 간선이 존재한다고 생각하면 된다. 앞서 보았던 가중 그래프를 파이썬 코드로 구현하면 다음과 같다.
graph = [[0, 10, 3, 2],
[0, 0, 0, 7],
[0, 0, 0, 6]
[0, 0, 0, 0]]행렬의 0번째 행에서 0번째 열은 0번 노드와의 연결을 나타낸다. 0번 노드는 자기 자신으로 돌아오는 링크를 가지고 있지 않으므로 인접하지 않은 것이며, 따라서 값은 0이다. 1번째 열은 1번 노드와의 연결이며, 가중치가 10으로 되어 있으므로 10을 넣어 준다. 마찬가지로 2번 노드와의 연결 가중치 3을, 3번 노드와의 연결 가중치 2를 순서대로 넣어 주면 0번 노드에 대한 연결 정보를 모두 표시하게 된다.
나머지 노드 역시 같은 방식으로 표시하는데, 1번 노드와 2번 노드는 서로 링크가 없으므로 INF로 표시한다.
이처럼 인접 행렬을 이용한 그래프의 구현은 구현이 상당히 쉽다는 것이 장점이다. 그리고 정점 i와 정점 j의 연결 여부를 확인하고자 한다면 matrix[i][j]가 0인지 1인지만 확인하면 되므로 O(1)이라는 시간만 소요된다는 장점도 있다.
그러나 치명적인 단점도 존재하는데, 전체 정점의 개수가 N개일 때 만약 정점 i에 연결된 모든 정점에 방문하고자 한다면 matrix[i][0]부터 matrix[i][N]까지 모두 확인해보아야 할 것이다. 정점에 비해 간선의 개수가 적다면(예컨대 정점은 1억 개인데 간선은 2개뿐이라면) 이러한 방법은 상당히 비효율적인 방법이 된다.
이러한 단점을 보완할 수 있는 표현 방식이 인접 리스트 방식이다.
인접 리스트를 이용한 구현
인접 리스트 방법은 그래프의 정점들을 리스트로 표현하는 것이다. 정점의 리스트를 만들고 해당 정점에 연결된 정점의 정보를 저장하는 식이다. 일반적인 그래프라면 정점 정보를 저장하고, 가중 그래프라면 해당 정점의 이름과 간선 가중치를 튜플 형태로 넣어주는 식이다.
※ 어떤 형태로 구현하느냐는 사람마다 차이가 있으며, 딕셔너리를 이용하는 경우도 있다.
위의 예와 동일한 그래프를 인접 리스트 형태로 구현하면 다음과 같을 것이다.
graph = [[(1, 10), (2, 3), (3, 2)], [(3, 7)], [(3, 6)] []]0번 정점은 1과 연결되어 있으며 가중치는 10이다. 2번과도 연결되어 있으며 가중치는 3이고, 3번과의 연결에서 가중치는 2이다. 1번 정점은 3번 정점과만 연결되어 있으며 가중치는 7이다. 이러한 방식으로 4개 정점에 대한 정보를 저장할 수 있다.
인접 리스트 방식은 실제로 연결된 정점에 대한 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있다. 따라서 전체 정점에 대한 탐색이 필요한 경우 각 정점별로 연결된 정점만 확인하는 것이 가능하므로 전체 간선의 개수만큼만 확인할 수있다. 따라서 모든 정점을 방문해보아야 하는 경우 인접 리스트로 그래프를 구현하는 것이 시간상 이점을 가지게 된다.
그러나 만약 정점 i와 j가 서로 연결되어 있는지 알고자 한다면? 거꾸로 matrix[i]의 벡터 전체를 순회하며 j를 성분으로 가지고 있는지 확인해야하므로 시간상 단점으로 작용한다.
두 연결 방식을 확인해 보면 어느 방식의 단점이 다른 방식의 장점이 되는 것을 알 수 있다. 따라서 해결해야 하는 문제의 성격에 따라 적절한 방식으로 그래프를 구현하는 것이 중요하다.
참고 자료
관련 코딩테스트 풀이
