그래프 간선의 분류
다음과 같이 어떤 방향 그래프가 주어졌을 때그래프를 깊이 우선 탐색하면서 따라가는 간선들만 모으면 트리 형태를 띠게 됩니다. 0번 정점에서 dfs함수를 호출해서 dfs함수가 따라가는 간선들을 오렌지 색으로 나타내고 각 정점의 방문 순서를 괄호로 표시했습니다. 이런 트리를 주어진 그래프의 DFS 스패닝 트리(DFS Spanning Tree)라고 합니다. 그래프의 DFS 스패닝 트리를 생성하고 나면 그래프의 모든 간선을 네가지 중 하나로 분류할 수 있습니다. 1. 트리 간선(tree edge) : 스패닝 트리에 포함된 간선2. 순방향 간선(forward edge) : 스패닝 트레에서 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선3. 역방향 간선(backward edge) : 스패닝트리에서 자손에서 선조..
알고리즘
2015. 10. 24. 01:16
최근에 달린 댓글
- Total
- Today
- Yesterday