네번째 자료구조 포스팅은 그래프이다!
그래프 Graph
그래프를 구성하는 요소는 두가지 이다.
그래프는 정점(vertex)과 간선(edge)으로 이루어진 자료구조 이고 다시 말하면 그래프는 여러 정점(vertex)들 같의 관계를 표현하는 조직도와 같다고 할 수 있겠다. 표현할 만한 예로는 노선도나, 지도와 같은 것들이 있겠다.
이후 다루게 될 트리 역시 그래프의 일종이라 할 수 있다. 트리와 달리 그래프에는 정점마다 간선이 존재할 수도 있고 없을 수도 있으며 부모-자식 관계라는 것이 존재하지 않는다!
그래프 용어
- 정점 vertex = 노드(node), 데이터가 저장되는 그래프 기본 원소
- 간선 edge = 링크(link), 정점간의 관계를 나타냄
- 인접 정점 adjacent vertex = 간선에 의해 연결된 정점 (A, C 는 서로 인접 정점)
- 단순 경로 simple path = 동일한 간선을 지나지 않는 경로
- 차수 degree = 무방향 그래프에서 한 정점에 인접한 정점의 수 (C의 차수는 2)
- 진출 차수 out-degree : 방향 그래프에서 한 정점에서 다른 정점으로 나가는 간선의 수
- 진입 차수 in-degree : 방향 그래프에서 외부에서 한 정점으로 들어오는 간선의 수
그래프 구현 방법
인접 행렬 Adjacency Matrix
인접 행렬은 2차원 배열로 그래프를 구현하는 방식이다. 간선이 존재하는 두 정점 칸은 1로 없는 칸은 0으로 채워주고 만약 가중치가 다른 그래프라면 해당 가중치 값을 넣어준다.
- 2차원 배열상에 그래프 정보다 모두 담겨 있기 때문에 간선의 존재 여부나 가중치를 알고 싶을 땐 바로 참조할 수 있다 : O(1)
- 간단하게 구현할 수 있다.
- 하지만 N^N 크기의 2차원 배열을 사용하기 때문에 메모리가 필요 이상으로 많이 사용될 수 있다. (10000개의 정점으로 구성된 그래프 내에 간선이 5개만 존재할 경우)
- 모든 간선 정보를 대입하는데에 시간이 걸린다 : O(N^N)
인접 리스트 Adjacency List
인접 리스트는 정점에 연결되어 있는 정점들만 리스트로 나타내는 그래프 표현 방식이다.
- 필요한 만큼의 메모리만 사용하기 때문에 메모리 낭비가 없고
- 정점들의 연결 정보를 확인하려 할 때는 간선의 갯수만큼의 탐색이 필요하다 O(N) (N = 정점에 연결된 간선 수)
- 이 과정이 인접 행렬에 비해서는 오래 걸릴 수 있다. (모든 노드가 10000개 인데 1번 노드에 9999개의 간선이 존재하는 경우 9999번째 인접 정점을 확인하는데는 9999번의 탐색이 필요)
그래프 종류
무방향 그래프
방향 그래프
가중치 그래프
완전 그래프
그래프 탐색
그래프에서 가장 중요한 부분이 바로 이 탐색이 아닐까? 정말 수도없이 사용하는 알고리즘이다!!
BFS
BFS, 넓이 우선 탐색이다. 정점을 기준으로 간선이 연결되어 있는 모든 정점들을 차례로 방문하고 찾고자 하는 정점을 만날 때 까지 반복한다. 일반적으로 Queue 를 사용하여 많이 구현한다.
DFS
DFS, 깊이 우선 탐색이다.
정점을 기준으로 간선이 연결되어 있는 정점 들 중 하나를 선택해 이동하고 다시 이동한 정점을 기준으로 다시 인접 정점을 선택한다. 연결되어있는 간선을 따라 찾고자 하는 정점을 만날 때 까지 진행하고 찾지 못하면 다시 이전 정점으로 돌아와 반복한다. 재귀함수를 통해서 구현하기도 하고 혹은 Stack 을 사용해 구현하기도 한다.
연결 성분 Connected Component
그래프의 연결 성분은 여러개의 노드의 집합에서 간선으로 연결된 각각의 그래프이다.
- 그래프 상의 임의의 노드를 선택해서 BFS 혹은 DFS 를 수행해 간선으로 연결되어 있는 정점들을 찾는다
- 방문되지 않고 남아있는 노드들 중 또 하나를 선택해서 반복하고
- 모든 노드가 방문될 때까지 진행해 연결 성분들을 완성할 수 있다.
신장 트리, Spanning Tree
신장 트리는 그래프 내 모든 정점이 연결되어 있으면서 사이클이 없는 트리를 말한다! 간선들을 통해서 모든 노드들이 연결되어 있고 그 안에서 사이클이 존재 하지 않아야 한다.
BFS 혹은 DFS 를 사용해 그래프를 탐색하는데 사용된 간선들만을 추려서 완성한다.
Reference
[자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree
[Algorithm] 자료구조 그래프(Graph)란 무엇인가?
