Dense BFS
inwooleeme 님이 알려준 밀집 그래프에서의 그래프 최단 거리를 구하는 방법. 관련 문제를 풀면서 확인해보자.
← 지식 노트
Graph.
Related Contents
기록 10
최근 업데이트 순Graph Basic
그래프는 다음과 같은 요소로 이루어져 있다.
Bipartite Matching
Bipartite Matching 관련 기록.
Dinic
Dinic 관련 기록.
Edmonds-Karp
Ford-Fulkerson 방법을 BFS로 구현한 것을 Edmonds-Karp Algorithm이라고 한다.
MCMF
MCMF 관련 기록.
Dijkstra
Dijkstra 관련 기록.
Floyd Warshall
Floyd Warshall 관련 기록.
SPFA
SPFA 관련 기록.
LCA
LCA는 Least Common Ancestor의 약자이다. Tree에서의 공통 조상을 찾는 문제에 사용되는 알고리즘이다. 공통 조상이 여러개 있을 수 있으므로, 그 중에 제일 빠른 조상을 LCA로 정의한다. input으로는 서로 다른 두 Node가 주어진다. 이 두 Node를 l과 r