【问题描述】
给定一个无回路的无向图（即树），设计一个动态规划算法，求出该图的最大独立集，并输出该集合中的各个顶点值。
1 package org.xiu68.exp.exp7; 2 3 import java.util.ArrayList; 4 5 public class Exp7_1 { 6 7 public static void main(String[] args) { 8 // TODO Auto-generated method stub 9 //运行结果 10 /* 11 树的最大独立集为: 4 12 顶点值为: 4 6 2 3 13 树的最小点覆盖为: 2 14 顶点值为: 5 1 15 */ 16 //由结果可知 最大独立集与最小点覆盖集合互为补集 17 ArrayList<Integer> vexs=new ArrayList<>(); 18 for(int i=1;i<=6;i++) 19 vexs.add(i); 20 //构造一个无向无环图 21 int[][] edges=new int[][]{ 22 {0,1,1,0,0,0}, 23 {1,0,0,0,1,0}, 24 {1,0,0,0,0,0}, 25 {0,0,0,0,1,0}, 26 {0,1,0,1,0,1}, 27 {0,0,0,0,1,0} 28 }; 29 MGraph<Integer> m=new MGraph<Integer>(6, 6, edges, vexs); 30 m.maxIndependentSet(); 31 System.out.println(); 32 m.minCoverSet(); 33 34 } 35 } 36 37 38 //邻接矩阵表示图、无向无环图 39 class MGraph<T>{ 40 public int vexNum; //顶点数量 41 public int edgeNum; //边数量 42 public int[][] edges; //邻接矩阵 43 public ArrayList<T> vexs; //顶点表 44 45 public int[][] maxDep; //最大独立集 46 public ArrayList<Integer> set; //最大独立集顶点序号 47 48 public int[][] minCover; //最小点覆盖 49 public ArrayList<Integer> minSet; //最小点覆盖顶点序号 50 51 public MGraph(int vexNum, int edgeNum, int[][] edges, ArrayList<T> vexs) { 52 this.vexNum = vexNum; 53 this.edgeNum = edgeNum; 54 this.edges = edges; 55 this.vexs = vexs; 56 57 maxDep=new int[vexNum][2]; 58 set=new ArrayList<>(); 59 60 minCover=new int[vexNum][2]; 61 minSet=new ArrayList<>(); 62 } 63 64 //最大独立集 65 public void maxIndependentSet(){ 66 independentSet(0, 0); 67 68 if(maxDep[0][0]>maxDep[0][1]) 69 System.out.println("树的最大独立集为: "+maxDep[0][0]); 70 else 71 System.out.println("树的最大独立集为: "+maxDep[0][1]); 72 73 System.out.print("顶点值为: "); 74 for(int i=0;i<set.size();i++) 75 System.out.print(vexs.get(set.get(i))+" "); 76 } 77 //求以child为根的树的最大独立集 78 //child:当前正在处理的结点 79 //parent:child的父结点 80 private void independentSet(int child,int parent){ 81 maxDep[child][0]=1; //当前结点放入独立集 82 maxDep[child][1]=0; //当前结点不放入独立集 83 84 for(int i=0;i<vexNum;i++){ 85 if(edges[child][i]==0 || i==parent) //如果顶点间不存在边或尾结点为父结点 86 continue; 87 independentSet(i, child); 88 89 //因为child加入了最大独立集，所以子结点不加入最大独立集 90 //以child为根的树的最大独立集的规模为 ( 1+ child的孙子结点的最大独立集的规模 ) 91 maxDep[child][0]+=maxDep[i][1]; 92 93 if(maxDep[i][0]>maxDep[i][1]) 94 maxDep[child][1]+=maxDep[i][0]; //加入子结点 95 else 96 maxDep[child][1]+=maxDep[i][1]; //不加入子结点 97 } 98 99 if(maxDep[child][0]>maxDep[child][1]) //比较加入child与不加入child的独立集大小，取较大者为结果 100 set.add(child); 101 } 102 103 //*********************************************************** 104 105 //最小点覆盖 106 public void minCoverSet(){ 107 coverSet(0,0); 108 if(minCover[0][0]<minCover[0][1]) 109 System.out.println("树的最小点覆盖为: "+minCover[0][0]); 110 else 111 System.out.println("树的最小点覆盖为: "+minCover[0][1]); 112 113 System.out.print("顶点值为: "); 114 for(int i=0;i<minSet.size();i++){ 115 System.out.print(vexs.get(minSet.get(i))+" "); 116 } 117 } 118 //求以child为根的树的最小点覆盖集合 119 //child:当前正在处理的结点 120 //parent:child的父结点 121 private void coverSet(int child,int parent){ 122 minCover[child][0]=1; //child放入最小点覆盖集合 123 minCover[child][1]=0; //child不放入最小点覆盖集合 124 125 for(int i=0;i<vexNum;i++){ 126 if(edges[child][i]==0 || i==parent) //如果顶点间不存在边或尾结点为父结点 127 continue; 128 129 coverSet(i,child); 130 131 //如果子结点i放入集合结果更小则把i放入集合 132 if(minCover[i][0]<minCover[i][1]) 133 minCover[child][0]+=minCover[i][0]; //子结点i放入集合 134 else 135 minCover[child][0]+=minCover[i][1]; //子结点i不放入集合 136 137 //若child不放入最小点覆盖集合，则其所有子结点都要放入最小点覆盖集合 138 minCover[child][1]+=minCover[i][0]; 139 140 if(minCover[child][0]<minCover[child][1]) //取最小值作为结果 141 minSet.add(child); 142 } 143 } 144 }