그래프에서 굴곡 정점을 찾는 방법은 무엇입니까?

Question

저는 그래프가 처음이기 때문에 그래프에서 관절 지점을 찾는 방법을 명확하게 설명 할 수있는 알고리즘을 얻지 못하고 있습니다. 누군가 설명해 주시겠습니까? 미리

Answer 1

고맙습니다 간단한 알고리즘 : 각 노드 N 정도

: 1. 거리 2 연결 컴포넌트들의 수를 계산하여 가라. dfs 또는 bfs 중 하나. 여전히 루프 인 경우 계속하십시오. 두 가지 경우 관절 점을 발견했습니다. 루프를 표시하고 계속하십시오.

이것은 2 차 시간으로 실행됩니다. 더 나은 알고리즘이 있는지 확실하지 않습니다.

---

편집 : http://algs4.cs.princeton.edu/41undirected/Biconnected.java.html

Answer 2

이 설명을 참조 : 내가 약간의 자바 소스 코드 on this site를 발견했다. 당신이 유용하다고 생각하기를 바랍니다.

http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/