그래프 이론 내용 정리
Graph
다양한 알고리즘 문제를 그래프 문제로 치환하여 풀이할 수 있기에 그래프 이론이 유용하게 활용될 수 있다.
graph를 프로그래밍 코드로 다루기 위해서 adjacency list를 만든다. adjacency list는 hash map을 통해 구현된다. key는 모든 노드이고, value는 각 노드와 edge로 연결된 모든 neighbor node다.
hash map의 시간 복잡도는 O(1)이므로 매우 효율적이다.
Directed graph
DFT(Depth first traversal), BFT(Breadth first traversal)은 Directed graph를 traversal(순회)하면서 탐색하는 탐색 알고리즘이다.
(traversal은 그래프나 트리와 같은 연결 구조에서 노드를 방문하는 데 활용된다.)
DFT은 깊이 우선 탐색으로 Stack 구조가 사용된다.
BFT은 너비 우선 탐색으로 Queue 구조가 사용된다.
-
Stack: Last in First Out(LIFO)
push를 통해 data가 top에 쌓이고, pop을 통해 data를 top에서 제거
한쪽에서 데이터가 들어오고 제거됨
-
Queue: First in First Out(FIFO)
push 또는 Enqueue를 통해 data가 들어오고, pop을 통해 data를 제거
한쪽에서는 데이터가 들어오고, 다른 쪽에서는 데이터가 제거됨
DFT 구현
출력 결과: a c e b d f
neighbor node들의 순서에 따라 출력 결과가 달라질 수 있지만, 여전히 BFT 탐색이다.
neighbor가 없는 node들이 base case 역할을 한다.
출력 결과: a c e b d f
BFT 구현
BFT는 iterative 방식으로만 구현할 수 있다.
출력 결과: a c b e d f
In JavaScript
shift: remove the first element
push: add element at the end
DFT와 BFT를 iterative하게 구현한 코드는 거의 동일하다.
딱 한 가지 다른 점은 DFT는 pop()을 통해 node를 제거하고, BFT는 shift()를 통해 node를 제거하는 것이다.
Has Path
cycle은 node 간의 연결이 끊임없이 이어지는 것을 의미하고, infinity loop를 이룬다.
acycle은 cycle이 존재하지 않는다는 의미이다.
source node가 f, destination node가 k일 때 f에서 출발해서 k까지 도달할 수 있는 경로가 있는지 판단하는 문제를 has path라고 한다.
src node에서 dst node로 도달할 수 있을 때 True다.
src node에서 dst node로 도달할 수 없을 때 False다.
n = node의 개수, e = edge의 개수라고 할 때, 시간 복잡도와 공간 복잡도는 아래의 두 방식으로 계산할 수 있다.
구현
Undirected graph
undirected graph를 왼쪽과 같이 나타낼 때는 두 node가 서로 연결되어 있음을 나타낸다.
프로그래밍할 때의 편의를 위해서 왼쪽 표현을 오른쪽과 같은 adjacency list로 변환한다.
BFT 구현
Has Path 및 구현
undirected graph에서 nodeA부터 nodeB까지의 has Path를 해결하는 코드다.
connected components count 및 구현
서로 연결되지 않아 독립되어 있는 node의 집합이 총 몇 개인지 세는 것이 connected components count다.
위의 코드를 통해 구현할 수 있다.
largest component 및 구현
largest component size는 4다.
shortest path 및 구현
shortest path problem에서는 DFT보다 BFT가 유리하다.
Island count 및 구현
W는 Water, L은 Land다. 위의 예시에서 Island는 4개다.
undirected graph 문제로 치환해서 다룰 수 있다.
minimum Island 및 구현
