[ALGO] 그래프 간선

👀 그래프 간선의 분류 (Graph Edge Classification)

DFS 스패닝 트리 또는 BFS 스패닝 트리를 생성하고 나면 그래프의 모든 간선은 네가지 중 하나로 분류된다.

✔ 트리 간선 (Tree Edge)

스패닝 트리에 포함된 간선

✔ 순방향 간선 (Forward Edge)

선조에서 자손으로 연결되지만 트리 간선이 아닌 간선

✔ 역방향 간선 (Backward Edge)

자손에서 선조로 연결되는 간선

✔ 교차 간선 (Cross Edge)

선조와 자손 관계가 아닌 정점들간에 연결된 간선

✔ DFS와 BFS에서의 간선

• DFS에서는 트리 간선과 역방향 간선만 존재
• BFS에서는 트리 간선과 교차 간선만 존재

👍 참고 사이트

1. 그래프 간선의 분류