알고리즘 - 그래프의 모든 커넥터 찾기

Question

정의 : 무향 그래프에서 버텍스 v는 커넥터이고 x와 w 사이의 모든 경로가 v를 통과하는 다른 두 개의 정점 x와 w가있는 경우입니다.

그래프를 저장하기 위해 인접 링크 된 목록을 사용하고 있습니다.

내 첫 번째 생각은 "덕, 잘 정점은 꼭지점의 유일한 이웃 인 경우 커넥터입니다."

비록 그것이 저 품질을 가지고 있지 않더라도 꼭지점이 커넥터 인 다른 사례가 있다는 것을 알고 있습니다.

나는 다른 모든 정점에 도달 할 수 있는지를 알기 위해 정점의 이웃의 모든 경로를 확인하는 솔루션을 생각해 냈습니다. 아마도 이것이 매우 시간이 많이 걸릴 것이라고 상상할 수 있습니다.

나는 더 빠른 알고리즘을 생각해 냈지만 그렇게 할 수는 없다. 누구든지이 문제를 해결하는 방법에 대한 힌트를 줄 수 있습니까?

Answer 1

그래프가 연결되어 있다고 가정합니다. 커넥터 정점을 제거하면 그래프의 연결을 끊어야합니다. 그런 다음 선형 시간에 dfs 또는 bfs를 사용하여 그래프의 구성 요소 수를 계산합니다. 구성 요소의 수가 변경되면 제거 된 정점 또는 노드가 커넥터임을 의미합니다.

각 정점에 대해이 알고리즘을 실행할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n^2)입니다.