그래프 알고리즘 (Graph Algorithm) 기초

Graph란? : 노드와 엣지(정점과 간선)으로 이루어진 자료구조를 의미한다. 그래프 알고리즘을 이용해, 매트릭스나 연결 리스트로 문제에서 주어진 노드들의 관계를 표현한다. 

그래프의 탐색 기법은 4가지로 나뉠 수 있다. 

출처 : https://m.blog.naver.com/occidere/220923695595

 

1. BFS 탐색

: 현재 정점과 연결된 정점들을 우선적으로 넓게 탐색!

큐(Queue)를 이용해서 구현, 즉 방문한 노드들을 차례로 저장한 후 꺼낼 수 있도록 한다. 

 

>큐가 뭐죠?

큐(Queue) : 컴퓨터의 기본적인 자료 구조 중 하나로, First in first out 구조로 데이터를 저장한다. 

스택과 반대개념

이진 트리의 level order과 동일 

chanhuiseok.github.io/posts/ds-2/

자료구조 - 이진 트리의 Level order traversal

 

2. DFS 탐색

: 현재 정점에서 연결된 정점을 하나 골라 파고 드는 탐색 기법이다. 

스택을 이용해 구현하며 직접 스택을 구현하거나 시스템 스택, 즉 재귀 호출을 사용할 수 있다. 

트리에서의 Inorder과 동일하다. 

- inorder 처리 과정

출처 https://emongfactory.tistory.com/61

자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. 어떤 노드를 방문했는지 여부를 반드시 검사하여야 한다. 

여기서 중요한 개념이 역추적(back tracking)이다. 

 

 

3. 다익스트라(Dijkstra Algorithm)

BFS의 응용, 어느 정점에서 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 큐 대신 최소 힙(Priority Queue)를 사용해 시간 단축을 구현한다. 시간복잡도가 O(V2)에서  O((V+E)logV)로 단축되는 효과가 있다. 

 

>최소 힙이 뭔가요?

힙은 일종의 트리로, 수의 집합에서 가장 작은 수나 가장 큰 수를 꺼내올 때 유용한 자료구조이다.

최소 힙과 최대 힙으로 나누어지는데, 최소 힙은 가장 작은 값이 루트이고, 최대 힙은 가장 큰 값이 루트이다. 

최소 힙으로 구현된 트리이다.

1이 가장 작으니까 루트이고, 완전 이진트리의 규칙에 따라 제일 왼쪽부터 노드가 추가될 수 있다.

이 숫자들을 배열의 인덱스로 생각하면 n번째 인덱스의 왼쪽 자식의 인덱스는 2n, 오른쪽 자식의 인덱스는 2n+1이 되는 것이다. 반대로 n번째 노드의 부모를 구하려면 n/2를 하면 된다. 

즉 다익스트라 알고리즘은 하나의 노드로부터 최단경로를 구하는 알고리즘이다. 

 

4. 플로이드 와샬

 

다익스트라 알고리즘이 하나의 노드로부터 최단 경로를 구하는 것이라면 플로이드 와샬은 가능한 모든 노드쌍들에 대해 최단 거리를 구하는 알고리즘이다. 시간복잡도는 O(V3)이고, 3중 for문을 이용해 각 정점마다 다른 정점까지의 최단거리를 모두 구한다. 

 

즉, 거쳐가는 모든 정점을 기준으로 알고리즘을 수행한다.