간선 분류

간선 분류는 그래프의 모든 간선을 특징에 따라 4가지의 종류로 분류하는 작업입니다.

4가지 종류는 아래와 같습니다.

1. 트리 간선 : 스패닝 트리에 포함된 간선

2. 순방향 간선 : 스패닝 트리의 선조에서 자손으로 연결되나 트리 간선이 아닌 간선

3. 역방향 간선 : 스패닝 트리의 자손에서 선조로 연결되는 간선

4. 교차 간선 : 위 분류를 제외한 나머지 간선

여기서의 스패닝 트리는 모든 정점을 포함하며, 사이클이 존재하지 않는 트리의 특성도 만족하는 부분 그래프를 뜻합니다.

(스패닝 트리에 대한 더 자세한 설명은 최소 스패닝 트리에서 진행합니다.)

단 한번의 DFS를 통해 스패닝 트리를 따라가면서 조건에 맞게 간선을 분류합니다.

이는 추후 그래프를 SCC로 분리하기 위해 사용하는 타잔의 알고리즘을 이해하는 데 도움이 됩니다.