algorithm
최소 정점 커버를위한 다항식 - 시간 경계 알고리즘

.NET Framework C Language C# Language C++ Java Language JavaScript MATLAB Language PHP Python Language Ruby Language

소개

연결된 무 방향성 그래프의 최소 정점 커버를 얻기위한 다항식 알고리즘입니다. 이 알고리즘의 시간 복잡도는 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