기본정리

1. kind of edge
   1. Tree edge: dfs의 결과로 완성된 트리의 모든 간선들
   2. Back edge: from descendent to ancestor(tree edge X)
   3. Forward edge: 트리에서 조상이 자식을 연결하는 tree edge가 아닌 간선들
   4. Cross edge: 이 외의 나머지 모든 간선
      

APPLICATIONS OF DFS

Topological sort

1. 정의: DAG에서 정점을 선형으로 정렬하는 것
   1. DAG: Directed acyclic(no-cycles) graph
2. 특징
   1. O(V+E)
   2. 여러 개의 topological sort(위상순서)가 나올 수 있음
      

connected components

1. 나누어진 각각의 그래프, maximal은 아니어도 되는 듯...!
   1. 그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있음
   2. 서로 연결되어 있는 여러 개의 고립된 부분 그래프 각각을 연결 성분이라고 부름
      

Strongly Connected Component

1. SCC: 모든 정점이 다른 모든 정점들에 대하여 방문할 수 있는 경우(= 두 정점 간의 경로가 존재)
2. 코사라주 알고리즘
   1. 주어진 방향 그래프의 역방향 그래프를 만듬(G^T)
   2. DFS(G^T) 적용, 결과로 나오는 각 트리가 SCC임

예시

critical path

1. 가장 오래걸리는 경로
2. 알고리즘

   1. 그래프 역방향으로 만들기, 가장 마지막에 있는 노드들에 done 노드 추가

   2. est 계산 조건

      1. 더 이상 진행할 다음 노드가 없을 경우 : est = 0
      2. 진행할 수 있는 다음 노드가 하나인 경우 : 다음 노드의 eft가 현재 노드의 est가 된다.
      3. 진행할 수 있는 다음 노드가 여러개인 경우 : 연결된 다음 노드들의 eft중 가장 큰 값이 현재 노드의 est가 된다. eft는 est + 간선 가중치(duration)로 계산한다.

      예시

      

bi-connected component

1. backtracking
   1. 해당 노드의 모든 edge들이 explored 되어, 해당 edge를 discovered 한 vertex로 돌아가는 것
2. 알고리즘