정리하기 위한 블로그 정리하기 위한 블로그

1. DFS 스패닝 트리 DFS 탐색하면서 탐색 순서에 따른 간선 분류와 만들어지는 트리 트리 간선 : 스패닝 트리에 포함되는 간선순방향 간선 : 선조에서 자손으로 연결되는 간선이지만 트리간선이 아닌 간선역방향 간선 : 자손에서 선조로 연결되는 간선 2. 절단점 찾기정의절단점 : 무향그래프에서 어떤 점의 인접한 간선을 모두 지웠을 때 컴포넌트가 두 개 이상으로 나눠지는 점  기차역, 라우터 등 절단점이 있으면 해당 점이 고장나면 전체 망이 고장난다. 절단점 찾는 방법 : DFS 스패닝 트리에서 어떤 정점 u의 서브트리 중에 u의 선조로 가는 역방향 간선이 하나라도 존재하지 않으면 절단점이 된다.-> 그럼 u의 1,2,3 서브트리 중 1이 선조로 가고 2가 1로 3이 2로 가면 u는 절단점인가? -> 아니..