이웃보다 작은 정도의 그래프에서 모든 정점 찾기

Question

나는 모든 정점 세트를 이웃보다 정도 작은 그래프에서 찾을 수있는 알고리즘을 작성하려고합니다. 나의 초기 접근법은 각 정점의 정도를 찾은 다음 각 정점의 정도를 이웃의 정도와 비교하여 목록을 통해 작업하는 것입니다. 불행히도, 이것은 매우 시간이 많이 걸리는 것처럼 보입니다. 이 세트를 찾는 더 효율적인 방법이 있습니까?

Answer 1

아마도 "이것은 시간이 많이 걸릴 수있는 것처럼 보이지만"더 나은 방법이 있습니다 :-)

그래프를 인접성 목록으로 저장했다고 가정 해 봅시다. 당신이 찾고있는 세트를 찾으려면 반드시 모든 가장자리를 봐야하므로 우리는 하한 알고리즘의 경우 ω (| e |)의. 모든 정점의 정도를 찾는 데 시간이 걸립니다 (| e |)는 시간이 걸립니다 (모든 모서리를 정확히 한 번 봅니다. 또 다른 증거는 ∑D (v) = 2 | e |)를 사용하는 것입니다. 각 정점의 정도를 모든 이웃과 비교하는 데 O (| e |) 시간 만 소요됩니다 (각 가장자리마다 한 번만 비교할 수 있음). 이는 알고리즘이 O (| e |) 시간 (약 2 | e | "단계"로 실행되지만 CPU 지침의 정확한 수는 하한을 충족합니다. 따라서 최악의 경우 "Brute-Force"알고리즘은 본질적으로 (최대 작은 상수)입니다. 최대한 빨리, 따라서 더 이상 최적화 할 가치가 없습니다.

실제 응용 프로그램을 위해이 작업을 수행하고 실제로 알고리즘에 너무 많은 시간이 걸린다면 프로파일 러를 사용하여 최적화 할 부분을 찾으십시오. 알고리즘의 두 번째 단계를 최적화하는 것이 중요하지 않습니다.

Answer 2

하나의 의견 - 방향이없는 그래프로 작업하는 경우 (감사해요, Brian R. Bondy), 일단 정점이 모든 이웃의 정도보다 적은 정도를 가지고 있다고 판단한 후에는 이웃을 확인할 필요가 없습니다. 그 지식을 사용하여 도움을주고 속도를 높이십시오.

Answer 3

나는 다음과 같이 방정 된 그래프에 대한 탐욕스러운 접근법을 상상할 것이다.

let Q = all nodes which haven't been checked (initialize all V)
let Q* = all nodes which satisfy the required condition (initialize to empty)
start with an arbitrary node, v in Q
while Q is not empty
    let minDeg be the minimum degree of all v's neighbors
    if degree(v) < minDeg
        add v to Q*
        remove all neighbors of v from Q
        remove v from Q
        set v = new arbitrary node, v in Q
    else
        remove v from Q
        set v = v's neighbor in Q of minimum degree

이 알고리즘은 각 반복에서 만족스러운 노드를 찾거나 새로운 노드를 더 적은 수준의 도로 확인하고 그래프에서 노드를 제거하기 때문에이 알고리즘은 약간 더 효율적 일 수 있습니다.

최악의 경우, 그것은 당신의 무차별 대기 알고리즘과 동일합니다. 그러나 평균적으로는 더 잘 수행해야한다고 생각합니다.