Edge separation 썸네일형 리스트형 [DFS] 그래프 단절점, 단절선 그래프의 단절점과 단절선이란? 단절점: 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다. 단절선: 단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다. 그럼 어떤게 단절점과 단절선을 빠르게 구할 수 있을까? 그래프 탐색 방법은 DFS를 이용하고, 현재의 정점(노드) 또는 간선을 제거했을 때 현재 정점의 하위에서 현재 정점보다 상위 노드로 접근이 가능하냐를 기준으로 단절점/단절선을 구분하는 방법을 사용한다. (그래프는 tree구.. 더보기 이전 1 다음