[Algorithm: 알고리즘] 04 Graph

목차

0. Introduction: 그래프 소개

1. What is graph? : 

- 그래프의 정의

- 그래프의 종류

- 그래프의 표현

- 성능 분석

- 그래프 알고리즘의 분류

2. DFS : 무방향 그래프에서의 깊이우선탐색

- 자료구조별 탐색법

- DFS

3. DFS : 유향 그래프에서의 깊이우선탐색

- 엣지의 종류

- Directed Acyclic Graph(DAG) : 유향 비순환 그래프

4. Strongly Connected Components(SCC) : 강한연결요소 

- 유향그래프에서의 연결성

- 알고리즘

5. Biconnected Components : 이중연결 요소

- Articulation point : 분절점

- Biconnected graph : 이중결합 그래프

- BCC에서 A-point찾기

- find-BCC 알고리즘 

6. Distance : 거리 계산 알고리즘

- 두 노드 사이의 거리

- 두 노드 사이의 최단 거리

7. BFS : 너비 우선 탐색

- 기본 전략 

- 최단거리 알고리즘

8. Single source shortest path : 단일 출발지 최단 경로

- 기본 전략 

- 간단한 접근법

- Alarm clock

- Dijkstar's Algorithm (1) (다익스트라 알고리즘) : 큐

- Dijkstar's Algorithm (1) (다익스트라 알고리즘) : 우선순위 큐

- Bellman-Ford's Algorithm (벨만포드 알고리즘)

9. All Pairs Shortest Path : 모든 쌍의 최단 경로

- 기본 개념 

- Floyd's Algorithm (플로이드 알고리즘)