728x90 반응형 Articulation Points1 알고리즘 - 단절점 (Articulation Points / Cut Vertices) 알고리즘 - 단절점 (Articulation Points / Cut Vertices) 1. 단절점이란? 무향 연결 그래프 G에서 하나의 정점과 연결된 간선들을 제거했을 때 두 개의 연결 그래프로 나뉘어 진다면 해당 정점은 단절점이다. 예를 들어 5에 있는 간선들을 모두 제거해도 그래프가 두 개로 나누어지지 않기 때문에 5는 단절점이 아니다. 그러나 4에 있는 간선들을 모두 제거할 경우 두 개의 연결 그래프로 나뉘어지기 때문에 단절점이다. 2. 단절점 찾기 - 무향 연결 그래프 G에서 어떤 정점 A에 연결된 정점들에 대해서 우회 경로 (정점 A를 거치지 않는 경로)가 없는 경우가 존재한다면 A는 단절점이다. orderV : 정점 V의 방문순서 lowV : 정점 V의 low (V 이후에 방문하는 정점들 중 .. 2021. 2. 3. 이전 1 다음 728x90 반응형
