유항 그래프이고, 사이클이 없어야 한다.
위상정렬 코드
최단 경로 문제 다익스트라 알고리즘 시작점부터 출발해 목표점까지의 거리 구하기 구하는 방법 우선순위 큐 사용 다익스트라 코드 All-Pairs Shortest Paths 모든 쌍에 대하여 최단 경로 구하는 알고리즘 증명 방법 다익스트라 알고리즘을 n번 호출(음의 가중치X)...
그래프 SCC(강연결요소) Strongly Connected Component A에서 B로 갈 수 있다면, B에서 A로도 갈 수 있는 성질 방향성이 존재하는 유향 그래프에서 모든 정점이 다른 모든 정점들에 대하여 방문할 수 있는 경우 증명 방법 그래프 G에서 한 정점 V를 선택 V에서 DFS를 통해 모...
그래프 네트워크 유량 문제 그래프에서 각 노드들 간의 용량(Capacity)가 정의되어 있을 때, 시작점(Source)에서 끝점(Target)까지 흐를 수 있는 최대 유량 구하는 문제 용어 소스(S, source): 시작점 싱크(T, sink): 끝점 정점(Vertex): 유량이 모이는 위치 ...
네트워크 유량 문제
문자열 압축
