subgraph.java

上海交通大学研究生算法分析课的作业.实现了<<算法引论-一种创造性方法>>(Udi Manber 黄林鹏 电子工业出版社)第五章中的大部分算法

//求图的度大于k的导出子图

//现在假定G=(V，E)是一个顶点数n>k+1的图。
//如果所有的顶点的度?k，则整个图满足要求，即为所求。
//否则，存在一个顶点v，其度<k。
//显然，在任何G的子图中，v的度都是<k；因此，v不属于任何满足该问题条件的子图。
//所以，我们把v和它相连的边删除，不影响定理的条件。
//当v被删除后，图中只有n-1个顶点，由归纳假设，知道如何对该问题求解。

//测试数据: 节点数：4，k值：2，边：(0,3),(0,1),(1,3),(1,2)
import java.io.*;
import java.util.*;
class SubGraph 
	{
		static InputStreamReader in;
		static BufferedReader reader;

		class Node
		{
		};

		static
		{
			in=new InputStreamReader(System.in);
			reader=new BufferedReader(in);
		}

		static String readString()
		{
			String s="";
			try
			{ 
				s=reader.readLine();
			}
			catch(IOException e)
			{
				System.out.println(e);
				System.exit(0);
			} 
			return s;
		}

		static int String2Integer(String s)
		{
			int i=0;
			try
			{
				i=Integer.parseInt(s);
			}
			catch(Exception e)
			{
				System.out.println("输入的数据类型不对，程序将退出");
				System.exit(0);
			}  
			return i;
		}

		static void SubGraph(int vNodeCount, int vK, int[][] vE)	//求出度不小于k的子图
		{
			int[][] iGraph = new int[vNodeCount][vNodeCount];
			int[] iNode = new int[vNodeCount];

			for (int i = 0; i < iNode.length; i++)		//构造图的节点存储结构
			{
				iNode[i] = i;
			}
			
			for (int i = 0; i < vE.length; i++)			//构造图的边存储结构
			{
				iGraph[vE[i][0]][vE[i][1]] = 1;
				iGraph[vE[i][1]][vE[i][0]] = 1;
			}
			
			boolean bIsDel = true;
			int x = iGraph.length;
			while (bIsDel)
			{
				bIsDel = false;
				int i = 0;
				boolean bNextLoop = true;
				while (bNextLoop)
				{
					bNextLoop = false;
					int iValue = 0;
					for (int j = 0; j < x; j++)
					{
						iValue = iValue + iGraph[i][j];
					}
					if (iValue < vK)
					{
						for (int p = i; p < x - 1; p++)
						{
							for (int q = 0; q < x - 1; q++)
							{
								iGraph[p][q] = iGraph[p + 1][q];
							}
							for (int q = 0; q < x - 1; q++)
							{
								iGraph[q][p] = iGraph[q][p + 1];
							}
							iNode[p] = iNode[p + 1];
						}
						i--;
						x--;
						bIsDel = true;
					}
					i++;
					bNextLoop = (i < x);
				}
				bIsDel = (bIsDel && x>0);
			}

			System.out.print("子图节点为：（　");
			for (int p = 0; p < x; p++)
			{
				System.out.print(iNode[p] + "　");
			}
			System.out.println("　）");

			System.out.print("子图边为：（　");
			for (int p = 0; p < x; p++)
			{
				for (int q = p; q < x; q ++)
				{
					if (iGraph[p][q] == 1)
					{
						System.out.print("(" + iNode[p] + "," + iNode[q] +") ");
					}
				}
			}
			System.out.println("　）");
		}

		public static void main(String _args[]) 
		{
			System.out.println("求图的度大于k的导出子图");
			System.out.print("请输入节点个数：");
			int iNodeCount = String2Integer(readString());
			System.out.print("请输入k的值：");
			int iK = String2Integer(readString());
			System.out.print("请输入边（格式如：(0,1),(2,3)）：");
			String strInput = readString();
			if (strInput.length() > 1)
			{
				strInput = strInput.substring(1, strInput.length()-1);
			}
			String[] strGroup = strInput.split("\\),\\(");

			int[][] iE = new int[strGroup.length][2];
			for (int i = 0; i < strGroup.length; i++)
			{
				String[] strEm = strGroup[i].split(",");
				if (strEm.length != 2)
				{
					System.out.println("输入的数据格式不对，程序将退出");
					System.exit(0);
				}
				iE[i][0] =String2Integer(strEm[0]);
				iE[i][1] =String2Integer(strEm[1]);
				if (iE[i][0] >= iNodeCount || iE[i][1] >= iNodeCount || iE[i][0] < 0 || iE[i][1] < 0)
				{
					System.out.println("输入的数据的值不对，程序将退出");
					System.exit(0);
				}
			}

			SubGraph(iNodeCount, iK, iE);
        }
    }