algorithm
최소 정점 커버를위한 다항식 - 시간 경계 알고리즘
수색…
소개
연결된 무 방향성 그래프의 최소 정점 커버를 얻기위한 다항식 알고리즘입니다. 이 알고리즘의 시간 복잡도는 O (n2)
매개 변수
변하기 쉬운 | 의미 |
---|---|
지 | 입력 된 비 직접 그래프 입력 |
엑스 | 버텍스 세트 |
기음 | 최종 정점 세트 |
비고
그래프의 모든 정점을 그 차수에 따라 내림차순으로 정렬하려면이 알고리즘에서해야 할 첫 번째 일입니다.
그 후에 당신은 그것들을 반복하고이 세트에 인접한 버텍스가없는 최종 버텍스 세트에 각각을 추가합니다.
마지막 단계에서 최종 꼭지점 세트를 반복하고이 세트에서 인접 꼭지점 중 하나를 갖는 모든 꼭지점을 제거합니다.
알고리즘 의사 코드
알고리즘 PMinVertexCover (그래프 G)
입력 그래프 G
출력 최소 정점 커버 세트 C
Set C <- new Set<Vertex>()
Set X <- new Set<Vertex>()
X <- G.getAllVerticiesArrangedDescendinglyByDegree()
for v in X do
List<Vertex> adjacentVertices1 <- G.getAdjacent(v)
if !C contains any of adjacentVertices1 then
C.add(v)
for vertex in C do
List<vertex> adjacentVertices2 <- G.adjacentVertecies(vertex)
if C contains any of adjacentVertices2 then
C.remove(vertex)
return C
C는 그래프 G의 최소 정점 커버
각도의 최대 값이 (n-1)이기 때문에 버킷 정렬을 사용하여 버텍스를 정렬 할 수 있습니다. 여기서 n은 버텍스의 수이고, 정렬의 시간 복잡도는 O (n)입니다.
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow