Havel–Hakimi algorithm
Havel–Hakimi算法是用来测试一个用度表示的图的序列是否能成图的算法. 成图算法中这个比较常见, 但是这个算法只能判断Simple Graph
输入是一个数字序列, 里面的每个数字都是图中点的度
排序取最大的数x, 然后看剩余x的数是否全是0, 如果是, 则可构成简单图, 如果不是, x个数每个都-1, 再排序取最大数. 一直这么做. 如果不都是0, 则不能构图.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
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"); } } |