👌 그래프 간선의 분류 (Graph Edge Classification)
DFS 스패닝 트리 또는 BFS 스패닝 트리를 생성하고 나면 그래프의 모든 간선은 네가지 중 하나로 분류된다
✔ 트리 간선 (Tree Edge)
스패닝 트리에 포함된 간선
✔ 순방향 간선 (Forward Edge)
선조에서 자손으로 연결되지만 트리 간선이 아닌 간선
✔ 역방향 간선 (Backward Edge)
자손에서 선조로 연결되는 간선
✔ 교차 간선 (Cross Edge)
선조와 자손 관계가 아닌 정점들간에 연결된 간선
✔ DFS와 BFS에서의 간선
- DFS에서는 트리 간선과 역방향 간선만 존재
- BFS에서는 트리 간선과 교차 간선만 존재
