반응형 edge 썸네일형 리스트형 [DFS] 그래프 간선의 분류 / 사이클(Cycle) 찾기 1. 깊이 우선 탐색(DFS)과 그래프 간선의 분류 어떤 방향 그래프를 깊이 우선 탐색(DFS)했을 때, 탐색이 따라간 간선들을 모으면 트리 형태를 가진다. 이때, 생성된 트리를 DFS 스패닝 트리 (DFS Spanning Tree)라고 부른다. DFS 스패닝 트리를 구성하고 나면 기존 그래프에서의 간선들을 네 종류로 나눌 수 있다. 1. 트리 간선 (Tree Edge) - DFS 스패닝 트리에 포함된 간선 2. 순방향 간선 (Forward Edge) - DFS 스패닝 트리의 선조(ancestor)에서 자손(descendant)으로 가는 간선이면서, 트리에 포함되지 않은 간선 3. 역방향 간선 (Back Edge) - DFS 스패닝 트리의 자손에서 선조로 가는 간선이면서, 트리에 포함되지 않은 간선 4... 이전 1 다음
