DFS 스패닝 트리 및 edge 의 유형

[1. 개요]

그래프를 대상으로 DFS 를 수행하였을 때,

사용 된 edge 를 모으면, 하나의 tree가 완성 되며,

이 tree 를 dfs 스패닝 트리라 한다.

 

특히, 연결 그래프를 대상으로 한 탐색 과정에서

이미 방문한 정점으로 향하는 edge 를 무시하지 않고,

이 정보를 수집하면

그래프에서 사용된 edge 를 아래와 같이 4가지 유형으로 분류 할 수 있다.

1. 트리 간선
2. 순방향 간선
3. 역방향 간선
4. 교차 간선

이러한 Edge 의 분류는 DFS 를 어떤 노드부터 시작하느냐에 따라 달라지게 된다.

 

또한, 무방향 그래프에서는 교차 간선은 존재하지 않고, 순방향/역방향 간선에 구분이 없다

• 무방향 그래프에서 교차 간선이 존재하지 않는 이유는
  # edge: {u, v} 가 교차 간선이 되기 위해서는
  # v 를 먼저 방문하고, 여기서 u 를 방문하지 않고 dfs 를 종료해야 하는데
  # 무방향 그래프이므로 v 는 u 가 방문되지 않았으면, 무조건 방문을 시도하게 된다.

---

[2. 트리 간선]

DFS 스패닝 트리에 속한 Edge

• DFS 탐색 중, u->v 에서 인접한 노드 v가 아직 방문되지 않아서 트리에 속하게 된 Edge

---

[3. 순방향 간선]

DFS 스패닝 트리에 속하지 않는 Edge 로, 조상에서 자손으로 연결되는 Edge. 

• u -> w -> v 가 트리 간선에 속할 때,
• 그래프에서 u ->v 로 가는 edge 가 있는 경우
• u -> v 는 순방향 간선이 된다.

---

[4. 역방향 간선]

역시, DFS 스패닝 트리에 속하지 않는 Edge 로, 자손에서 조상으로 연결되는 Edge

• u -> w -> v 가 트리 간선에 속할 때,
• 그래프에서 v -> u 로 가는 edge 가 있는 경우
• v -> u 는 역방향 간선이 된다. 

---

[5. 교차 간선]

트리 간선, 순방향 간선, 역방향 간선 외 모든 간선이 교차 간선에 속한다.

• 트리에서 조상과 자손 관계가 아닌 정점들 간에 연결 된 edge

---

[6. 예제]

 

A. 트리 간선

=> 스패닝 트리에 포함된 Edge

=> 굵은 실선 화살표

 

B. 순방향 간선

=> 스패닝 트리에서 조상에서 자손으로 연결 되지만, 트리 간선이 아닌 Edge
=> 검정색 점선 화살표

 

C. 역방향 간선

=> 스패닝 트리에서 자손에서 조상으로 연결되는 Edge, 트리 간선이 아닌 Edge
=> 빨간색 점선 화살표

 

D. 교차 간선

=> 트리 간선, 순방향 간선, 역방향 간선이 아닌 모든 Edge
=> 파란색 점선 화살표

---

[7. Edge 유형을 분류하는 방법]

아래 코드는 방향 그래프를 대상으로 dfs 수행 시 edge 유형을 분류한다.