━━━━ ◇ ━━━━
-/algo

[ALGO] 그래프 간선

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

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

✔ 트리 간선 (Tree Edge)

스패닝 트리에 포함된 간선

✔ 순방향 간선 (Forward Edge)

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

✔ 역방향 간선 (Backward Edge)

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

✔ 교차 간선 (Cross Edge)

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

✔ DFS와 BFS에서의 간선

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

👍 참고 사이트

  1. 그래프 간선의 분류


'- > algo' 카테고리의 다른 글

[ALGO] 프로그래머스: 프린터  (0) 2021.06.16
COMMENT
1