데드락 감지
-
그래프 간선의 분류 간단 정리컴퓨터 과학/자료구조와 알고리즘 2021. 9. 14. 22:41
참고 https://rebro.kr/71 https://hy38.github.io/about-edges-in-graph https://bowbowbow.tistory.com/1 https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm 설명 아래와 같은 그래프가 있습니다. 1번 정점부터 깊이 우선으로 탐색을 시작하면 다음과 같은 스패닝 트리가 나옵니다. 스패닝 트리를 연결하고 있는 간선을 스패닝 트리 간선이라고 합니다. 스패닝 트리에는 순환이 없습니다. 스패닝 트리는 이미 방문한 노드는 방문하지 않기 때문에 (5, 1), (6, 4), (6, 3), (1, 7) 간선은 스패닝 트리에 포함되지 않습니다. 여기에서 순방향 간선, 역..