알고리즘 공부 - 그래프
안녕하세요. yeTi입니다.
오늘은 알고리즘 공부 중 그래프(graph)에 대해 학습한 내용을 공유하려고 합니다.
강의 : 권오흠 교수님의 2015 봄학기 알고리즘
개요
그래프는 노드와 엣지, 두 집합으로 구성된 자료구조입니다.
그래프의 종류에는 무방향 그래프, 방향 그래프, 가중치 그래프가 있습니다.
그래프는 인접 행렬과 인접 리스트로 표현 가능합니다.
인접 행렬은 n*n 크기의 2차원 행렬로 표현하는 방식으로 저장 공간은 O(n^2)의 크기를 가지고, 인접한 모든 노드를 찾는 시간은 O(n), 엣지의 존재 여부를 찾는 시간은 O(1)의 특성을 가집니다.
인접 리스트는 노드 집합을 표현하는 1차원 배열과 각 노드마다 인접한 노드들을 연결 리스트로 표현한 방식입니다. 저장 공간은 O(n+m)의 크기를 가지고, 인접한 모든 노드를 찾는 시간은 O(degree(v)), 엣지의 존재 여부를 찾는 시간은 O(degree(u))의 특성을 가집니다.
방향 그래프에서 인접 행렬은 비대칭 형태를 가지고 인접 리스트는 m개의 노드를 가집니다. (무방향 그래프에서는 2m개의 노드를 가짐)
가중치 그래프에서 인접 행렬을 표현할 때의 값은 가중치를 넣는다는 특징이 있고, 인접 리스트에서는 가중치 정보를 추가하는 방식으로 확장해야 합니다.
추가적으로 경로, 연결된(connected) 그래프, 연결 요소(connected component)라는 개념이 존재합니다.
경로는 특정 두 노드간 이어진 엣지를 가진다면 해당 엣지들을 경로라고 표현합니다. 그리고 모든 노드들이 경로를 가진다면 연결된(connected) 그래프라고 표현하며, 각각의 연결된(connected) 그래프를 연결 요소(connected component)라고 표현합니다.
순회 (Traversal)
그래프를 순회하는 방법에는 BFS(Breadth-First Search, 너비우선순회)와 DFS(Depth-First Search, 깊이우선순회)가 있습니다.
BFS
BFS는 앞서 트리에서 Level-Order Search 할 때 언급한 바 있습니다. 노드에서 인접한 노드들을 먼저 검색하는 방식입니다.
방향 그래프와 무방향 그래프에 상관없이 BFS를 하면서 각 노드의 최단 경로의 길이를 구할 수 있습니다. 최단 경로의 길이는 출발 노드로부터 엣지의 갯수입니다.
BFS를 연결하는 엣지를 활용하면 트리로 볼 수 있습니다. 이를 BFS 트리 라고 합니다. BFS 트리에서 root 에서 특정 노드까지의 경로는 최단 경로를 의미합니다.
BFS를 인접 리스트로 구현할 경우, 모든 노드를 탐색하는 시간 O(n)에 각 노드가 가진 엣지를 탐색하는 시간 O(2m, 무방향 그래프에서)을 합하여 최종적인 시간복잡도는 O(n+m)입니다.
만일 그래프가 disconnected 이거나 방향 그래프면 한번의 탐색으로 모든 노드를 방문하지 않을 경우가 생기므로 모든 모드를 방문했는지 확인할 필요성이 있습니다.
DFS
DFS 또한 앞서 트리에서 In-Order Search, Pre-Order Search, Post-Order Search 할 때 언급한 바 있습니다. 노드에서 다음 level을 먼저 검색하는 방식입니다.
DFS를 인접 리스트로 구현할 경우, BFS와 마찬가지로 모든 노드를 탐색하는 시간 O(n)에 각 노드가 가진 엣지를 탐색하는 시간 O(2m, 무방향 그래프에서)을 합하여 최종적인 시간복잡도는 O(n+m)입니다.
만일 그래프가 disconnected 이거나 방향 그래프면 BFS와 동일하게 한번의 탐색으로 모든 노드를 방문하지 않을 경우가 생기므로 모든 모드를 방문했는지 확인할 필요성이 있습니다.
DAG (Directed Acyclic Graph)
DAG는 방향 사이클(directed cycle)이 없는 방향 그래프를 의미합니다.
DAG인 경우 작업들간 우선순위를 정할 수 있는 위상정렬(topological ordering)을 할 수 있습니다.
위상정렬 알고리즘에는 대표적으로 두 가지 종류가 존재하는데요. 첫 번째는 indegree가 0인 노드를 출력하고 해당 노드의 outgoing을 모두 제거하는 방식입니다. 두 번째 방식은 임의의 노드에 대해 DFS를 수행 후 DFS path를 정렬할 배열의 마지막부터 할당하는 방식입니다. 두 방식 모두 시간복잡도는 O(n+m)을 가집니다.