헬창 개발자

브릿지란 단절선, 절단선을 의미하며 그래프가 2개로 나눠지는 간선을 의미한다. 다음과 같은 그래프가 있다. 이 그래프에 단절선은 어떻게 찾을까?? 우리가 필요한 자료구조는 순회 체크 리스트, 현재 정점, 부모 정점, 브리지를 담을 리스트, 우회로 변수, (a, b) = (본인 순번, 주변 최소 순번)이다. 이제 알고리즘을 살펴보자 요약은 다음과 같다. # 자식 노드에서 부모 노드로 역으로는 검사 불가 (a, b)=(순번, 주변 최소 순번)를 비교하여 탐색하고 자식 노드의 b가 부모 노드의 a와 같으면 다른 노드를 통해 부모로 갈 수 있기 때문에 우회로가 있다고 판단하여 브리지가 아니게 되고 자식 노드의 b가 부모 노드의 a 보다 크면 우회로가 없기 때문에 브리지라고 판단한다. 정점 1에서 탐색을 시작한다..