그래프란 정점(Vertex) 혹은 노드(Node)간의 관계를 표현하는 자료구조이다.
그래프 G=(V, E)로 정의하는데, V(Vertex)는 그래프에 있는 정점들의 집합, E(Edge)는 정점을 연결하는 간선들의 집합을 의미한다.
그래프 관련 용어
- 정점(vertex): 노드(node)라고도 하며 데이터가 저장되는 위치
- 간선(edge): 링크(link)라고도 하며 정점을 연결하는 선
- 인접 정점(adjacent vertex): 간선에 의해 직접 연결되는 정점
- 경로(path): 정점 A부터 정점 B까지 갈 수 있는 길을 나열한 것
- 단순 경로(simple-path): 경로 중 반복되는 정점이 없는 경로
- 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진출 차수(out-degree): 방향 그래프에서 정점에서 나가는 간선
- 전입 차수(in-degree): 방향 그래프에서 정점으로 들어오는 간선
- 사이클(cycle): 경로의 시작과 끝이 같은 경로
특징
- 그래프는 네트워크 모델 -> 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해 가능하다.
- 2개 이상의 경로가 가능 -> 정점 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
- 그래프 순회는 DFS, BFS로 가능하다.
- 그래프에는 루트 노드, 부모-자식이라는 개념이 존재하지 않는다.
- 그래프에 따라 간선이 있을수도 있고 없을수도 있다.
- 트리는 그래프의 한 종류이다.
그래프 구현
그래프를 구현하는 방법에는 인접 행렬(Adjacency Materix)와 인접 리스트(Adjacency List)방식이 존재한다.
인접 행렬(Adjacency Materix)
그래프의 연결 관계를 이차원 배열로 나타내는 방식
인접 행렬 adj[i][j]에 대해 두 정점을 연결하는 간선이 있으면 1, 아니면 0을 채운다.
장점
- 구현이 쉽다.
- 두 정점을 연결하는 간선을 조회할 때 시간 복잡도는 O(1)이 나온다.
단점
- 간선의 수와 상관없이 배열의 크기가 항상 n2이므로 메모리 공간이 낭비된다.
- 모든 간선의 수를 알아내려면 이차원 배열을 모두 확인해야 하므로O(n2)의 시간이 소요된다.
인접 리스트(Adjacency List)
그래프의 연결 관계를 연결리스트(Linked List)로 표현하는 방식
정점의 개수만큼 인접 리스트가 존재하며, 각각의 리스트에는 인접한 정점 정보가 저장된다.
장점
- 인접 행렬에 비해서 메모리 측면에서 효율적이다.
- 정점의 연결 정보를 탐색할 때 O(n)의 시간복잡도가 나온다.
단점
- 비교적 구현이 어렵다.
- 두 정점을 연결하는 간선을 조회하기 위해서는 인접 행렬에 비해 오래걸린다.
종류
그래프는 간선의 종류에 따라 여러 종류로 나뉘게 된다.
무방향 그래프
두 정점을 연결하는 간선에 방향이 없으며, 양 방향 이동이 가능한 그래프
경로를 표시할 때 (A, B)로 표현함
방향 그래프
두 정점을 연결하는 간선에 방향이 존재하며, 간선의 방향으로만 이동이 가능한 그래프
경로를 표시할 때 <A, B>로 표현함
가중치 그래프
두 정점을 이동할 때 필요한 비용(cost) 또는 가중치(weight)를 표시한 그래프
네트워크(network)라고 불리기도 함
완전 그래프
모든 정점이 간선으로 연결돼있는 그래프
무방향 완전 그래프의 정점의 수가 n이라면, 전체 간선의 수는 n*(n-1)/2가 된다.
그래프 탐색
그래프에서 첫 정점부터 마지막 정점까지 한 번씩 방문하는 것을 그래프 탐색이라 함
탐색하는 방법에 따라서 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)로 나눌 수 있다.
깊이 우선 탐색(Depth First Search)
깊이 우선 탐색은 특정 노드에서 시작하여 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행
간단한 재귀호출을 사용하거나 스택을 사용하여 구현
너비 우선 탐색(Breadth First Search)
너비 우선 탐색은 시작정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선방문하는 방법
일반적으로 Queue를 사용하여 지금 위치에서 갈 수 있는 모든 정점을 Queue에 넣는 방식으로 구현한다.
Reference
