顶点覆盖问题近似计算

算法分析与设计老师布置的代考试作业，其中一道题目是顶点覆盖问题近似计算，想了挺长时间，想到了一个思路，感觉自己好菜。。。

Description
	无向图G=(E，V)，寻找V的一个最小子集V’，使得图中所有边至少有一个顶点在集合V’中。输出V’包含的顶点数。若最优解为C，输出的近似解C*接受范围是[C, 1.5*C]。
Input
 第1行有两个正整数n和m，1<=n<=100, 1<=m<=1000，分别代表图中顶点个数和边个数。
 第2行至第m+1行分别有2个整数a[i]，b[i]，表示图中的一条边，其顶点编号是a[i]和b[i]，编号从0开始。
Output
 第一行输出近似解正整数C*。
 接下来一行输出C*个正整数，表示每个顶点的编号，顺序任意。
Sample Input
4 5
0 1
1 2
2 3
0 2
1 3

Sample Output
2
1 2

首先构建出无向图，在构建图的同时标记每个顶点的度数，通过对题意的分析得出需找到的集合一定满足其内全部顶点度数之和大于等于总边数的结论。然后就是采用了贪心算法和枚举算法。（我觉得是贪心和枚举，具体我这个代码用到了啥我不确定，菜鸟上路，大佬勿喷）

算法过程：
第1步，将所有无向图中顶点按照其度数有大到小的顺序排列；
第2步，采用枚举法列举出所有满足度数之和大于无向图边数的集合；
第3步，每列举出一个测试集合，测试其是否满足顶点覆盖问题的要求，若满足则暂存集合；
第4步，重复2、3步，若有满足要求且集合内顶点数量更少的集合则替换掉之前的暂存集合，直到遍历完全部可能集合或者满足近似解范围为止。

import java.util.*;
public class Main {
	public static int flag;
	static ArrayList<String> map = new ArrayList<String>();					//存放所有的边
	static LinkedList<Integer> trueList = new LinkedList<Integer>();		//存放最终的最优结果
	static LinkedList<Integer> tmpList = new LinkedList<Integer>();			//存放递归过程中的临时集合
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), m = sc.nextInt();							//n,m分别代表点数和边数
		flag = n;
		int[] nNum = new int[n];										//存每个顶点的度
		for(int i=0;i<m;i++) {
			int tmp1 = sc.nextInt(), tmp2 = sc.nextInt();				//暂存一条边连接的两个顶点
			nNum[tmp1]++;												//顶点度数自增
			nNum[tmp2]++;
			map.add(tmp1+"-"+tmp2);										//存入边
		}
		LinkedList<Integer> port = new LinkedList<Integer>();			//按照降序存放顶点
		LinkedList<Integer> portNum = new LinkedList<Integer>();		//按照降序存放顶点的度
		port.add(0);
		portNum.add(nNum[0]);
		for(int i=1;i<n;i++) {
			if(nNum[i]>=portNum.get(0)) {
				port.add(0,i);
				portNum.add(0,nNum[i]);
			}
			else if(nNum[i]<=portNum.get(portNum.size()-1)) {
				port.add(port.size()-1,i);
				portNum.add(portNum.size()-1, nNum[i]);
			}
			else {
				for(int j=1;j<port.size();j++) {
					if(nNum[i]>=portNum.get(j)) {
						port.add(j,i);
						portNum.add(j,nNum[i]);
						break;
					}
				}
			}
		}
		Recursion(0, m, port, portNum, 0);								//递归枚举所有的可能组合
		System.out.println(flag);
		for(int i=0;i<flag;i++) {
			System.out.print(trueList.get(i)+" ");
		}
	}
	
	static void Recursion(int i, int m, LinkedList<Integer> port, LinkedList<Integer> portNum, int Sum) {
		int ASum = Sum + portNum.get(i);
		tmpList.add(port.get(i));
		if(ASum>=m && Judge(tmpList)==1 && tmpList.size()<flag) {
				trueList = tmpList;
				flag = trueList.size();
		}
		else if(i<port.size()-1){
			Recursion(i+1, m, port, portNum, ASum);
			tmpList.remove(tmpList.size()-1);
			Recursion(i+1, m, port, portNum, Sum);
		}
	}
	
	static int Judge(LinkedList<Integer> tmpList) {				//判断是否满足覆盖的要求
		for(int i=0;i<map.size();i++) {
			String[] tmpstr = map.get(i).split("-");
			if(tmpList.indexOf(Integer.parseInt(tmpstr[0]))==-1 && (tmpList.indexOf(Integer.parseInt(tmpstr[1]))==-1)) {
				return 0;
			}
		}
		return 1;
	}
}