그래프와 관련된 심화 알고리즘을 알아보기 전에, 그래프의 간선을 몇 가지의 종류로 구분하는 방법을 알아봅시다.
DFS트리 생성
위 그래프에서 1번 정점부터 시작해 dfs 탐색을 실행하면 아래와 같은 트리가 나오게 됩니다.
괄호 안에 있는 숫자는 각각 discovery time과 finish time을 나타냅니다.
discovery time은 해당 정점을 방문한 시간이고, finish time은 해당 정점을 탈출한 시간입니다.
discovery time을 dt[i], finish time을 ft[i]라고 해봅시다.
dt와 ft를 이용해 간선들을 4가지로 구분할 수 있습니다.
tree edge
그래프의 간선(u -> v) 중, dfs tree에 속하는 간선을 의미합니다. tree edge를 타고 가면 dfs tree 상의 자식에게 갈 수 있습니다.
dt[u] < dt[v] && ft[u] > ft[v] 를 만족합니다.
back edge
그래프의 간선(u -> v) 중, dfs트리 상에서 v가 u의 조상인 간선을 의미합니다. back edge를 타고 가면 dfs tree상의 조상에게 갈 수 있습니다.
dt[u] > dt[v] && ft[u] < ft[v] 를 만족합니다.
forward edge
그래프의 간선(u -> v) 중, v가 u의 자손이지만 tree edge에는 속하지 않는 간선을 의미합니다. forward edge를 타고 가면 dfs tree상의 자손에게 갈 수 있습니다.
dt[u] < dt[v] && ft[u] > ft[v] 를 만족합니다.
cross edge
위 3가지 경우가 아니라면 cross edge입니다. 그래프의 간선(u -> v) 중, u가 v의 조상도 아니고, v가 u의 조상도 아닌 경우를 의미합니다.
dt[u] > dt[v] 를 만족합니다.
위에서 본 그래프와 dfs tree의 간선을 분류해봅시다.
앞으로 이런 간선들의 분류를 통해 SCC나 단절점, 단절선과 같은 요소들을 구하는 방법을 알아볼 것입니다.