根据总人数建立顶点数量为总人数的无向图,顶点之间有边相连表示两个人相互认识，没有边则表示不认识。对于每一个顶点v,设d(v)表示顶点的度，若d(v)<5,即v认识的人数少于5，则不邀请v，若d(v)>总人数-6,即v认识的人数大于(总人数-6)个，即v不认识的人少于5个，这种情况也不邀请v，给定一个相互配对列表，循环遍历列表，找出不邀请的人，从列表中删除，若找不到删除的人则结束循环，剩下的即为要邀请的人。
1 package org.xiu68.ch05.ex10; 2 3 import java.util.ArrayDeque; 4 5 public class Ex5_28 { 6 7 public static void main(String[] args) { 8 // TODO Auto-generated method stub 9 int[][] guest=new int[13][13]; 10 //0~5之间相互认识，不认识6~11 11 //6~11之间相互认识,不认识0~5 12 //12不认识任何一个人 13 //结果应该邀请除了12之外的所有人 14 for(int i=0;i<guest.length-1;i++){ 15 if(i<=5){ 16 for(int j=0;j<guest[i].length-1;j++){ 17 if(j<=5 && i!=j) 18 guest[i][j]=1; 19 else 20 guest[i][j]=0; 21 } 22 }else{ 23 for(int j=0;j<guest[i].length-1;j++){ 24 if(j>5 && i!=j) 25 guest[i][j]=1; 26 else 27 guest[i][j]=0; 28 } 29 } 30 }//for 31 maxGuest(guest, 13); 32 /*运行结果*/ 33 34 //邀请的客人为: 35 //0 1 2 3 4 5 6 7 8 9 10 11 36 } 37 38 //guest:客人的相识配对表 39 //客人总数 40 public static void maxGuest(int[][] guest,int num){ 41 42 int invidedNum=num; //记录邀请的人数 43 boolean[] invided=new boolean[num]; //记录邀请的客人,邀请为true 44 for(int i=0;i<num;i++) 45 invided[i]=true; 46 47 ArrayDeque<Integer> notInvidedQueue=new ArrayDeque<>(); //记录不邀请的客人 48 49 do{ 50 51 for(int i=0;i<notInvidedQueue.size();i++) 52 invided[notInvidedQueue.poll()]=false; //将不邀请的客人标记为false 53 54 for(int i=0;i<num && invided[i]==true;i++){ 55 int recognizeNum=0; //第i个人相识的人数 56 for(int j=0;j<num && invided[j]==true;j++){ 57 if(guest[i][j]==1) 58 recognizeNum++; 59 }//for2 60 61 //如果认识的人数少于5个 62 //或者如果认识的人数大于(总人数-6)个，即不认识的人少于5个 63 //则不邀请这个人 64 if(recognizeNum<5 || recognizeNum>(invidedNum-6)){ 65 notInvidedQueue.add(i); 66 invidedNum--; 67 } 68 }//for1 69 70 }while(!notInvidedQueue.isEmpty()); 71 72 System.out.println("邀请的客人为:"); 73 for(int i=0;i<num;i++){ 74 if(invided[i]) 75 System.out.print(i+" "); 76 } 77 System.out.println(); 78 } 79 80 }