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");
}
}