Havel–Hakimi algorithm

Havel–Hakimi算法是用来测试一个用度表示的图的序列是否能成图的算法. 成图算法中这个比较常见, 但是这个算法只能判断Simple Graph

输入是一个数字序列, 里面的每个数字都是图中点的度

排序取最大的数x, 然后看剩余x的数是否全是0, 如果是, 则可构成简单图, 如果不是, x个数每个都-1, 再排序取最大数. 一直这么做. 如果不都是0, 则不能构图.

import java.util.*; 

public class HavelHakimi {
    public boolean Hakimi(int[] arr) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int n : arr)
            pq.add((n));
         while (!pq.isEmpty()){
            int n = pq.poll();
            if(n == 0)
                return true;
            if(n > pq.size())
                return false;
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++){
                int m = pq.poll();
                if(m < 0)
                    return false;
                list.add(m - 1);
            }
            for(int l : list)
                pq.add(l);
        }
        return false;
    }
    public static void main(String[] args) {
        int[] yes = new int[]{3, 3, 3, 3};
        int[] no = new int[]{3, 2, 1, 0};
        HavelHakimi h = new HavelHakimi();
        System.out.println(h.Hakimi(yes) +" should be yes");
        System.out.println(h.Hakimi(no) +" should be no");
    }
}