//类名：Vertex
//属性：
//方法：
class Vertex{
	public char label;	//点的名称，如A
	public boolean wasVisited;
	
	public Vertex(char lab){	//构造函数
		label = lab;
		wasVisited = false;
	}
}

//类名：Graph
//属性：
//方法：
class Graph{
	private final int MAX_VERTS = 20;
	private Vertex vertexList[];	//顶点列表数组
	private int adjMat[][];			//邻接矩阵
	private int nVerts;					//当前的顶点
	private char sortedArray[];
	
	public Graph(){	//构造函数
		vertexList = new Vertex[MAX_VERTS];
		adjMat = new int[MAX_VERTS][MAX_VERTS];
		nVerts = 0;
		for(int j=0;j<MAX_VERTS;j++){
			for(int k=0;k<MAX_VERTS;k++)
				adjMat[j][k] = 0;
		}
		sortedArray = new char[MAX_VERTS];
	}
	
	public void addVertex(char lab){	//添加新的顶点，传入顶点的lab，并修改nVerts
		vertexList[nVerts++] = new Vertex(lab);
	}
	
	public void addEdge(int start,int end){	//添加边，这里是无向图
		adjMat[start][end] = 1;
		//adjMat[end][start] = 1;
	}
	
	public void displayVertex(int v){	//显示顶点
		System.out.print(vertexList[v].label);
	}
	
	public int getAdjUnvisitedVertex(int v){	//返回一个和v邻接的未访问顶点
		for(int j=0;j<nVerts;j++)
			if(adjMat[v][j] == 1 &amp;&amp; vertexList[j].wasVisited == false){
				return j;
			}
			return -1;	//如果没有，返回-1
	}
	
	public void dfs(){	//深度搜索
		Stack<Integer> theStack = new Stack<Integer>();
		vertexList[0].wasVisited = true;
		displayVertex(0);
		theStack.push(0);	//把根入栈
		
		while(!theStack.empty()){
			int v = getAdjUnvisitedVertex(theStack.peek());//取得一个和栈顶元素邻接的未访问元素
			if(v == -1)		//如果没有和栈顶元素邻接的元素，就弹出这个栈顶
				theStack.pop();
			else{				//如果有这个元素，则输出这个元素，标记为已访问，并入栈
				vertexList[v].wasVisited = true;
				displayVertex(v);
				theStack.push(v);
			}
		}
		for(int j=0;j<nVerts;j++)		//全部置为未访问
			vertexList[j].wasVisited = false;
	}
	
	public void bfs(){	//广度搜索
		Queue<Integer> theQueue = new LinkedList<Integer>();
		vertexList[0].wasVisited = true;
		displayVertex(0);
		theQueue.offer(0);	//把根入队列
		int v2;
		
		while(!theQueue.isEmpty()){
			int v1 = theQueue.remove();//v1记录第1层的元素，然后记录第2层第1个元素...
			
			while((v2=getAdjUnvisitedVertex(v1)) != -1){//输出所有和第1层邻接的元素，输出和第2层第1个元素邻接的元素...
				vertexList[v2].wasVisited = true;
				displayVertex(v2);
				theQueue.offer(v2);
			}
		}
		
		for(int j=0;j<nVerts;j++)		//全部置为未访问
			vertexList[j].wasVisited = false;
	}
	
	public void mst(){	//基于深度搜索的最小生成树
		Stack<Integer> theStack = new Stack<Integer>();
		vertexList[0].wasVisited = true;
		theStack.push(0);	//把根入栈
		
		while(!theStack.empty()){
			int currentVertex = theStack.peek();	//记录栈顶元素，当有为邻接元素的时候，才会输出
			int v = getAdjUnvisitedVertex(theStack.peek());//取得一个和栈顶元素邻接的未访问元素
			if(v == -1)		//如果没有和栈顶元素邻接的元素，就弹出这个栈顶
				theStack.pop();
			else{				//如果有这个元素，则输出这个元素，标记为已访问，并入栈
				vertexList[v].wasVisited = true;
				theStack.push(v);
				
				displayVertex(currentVertex);
				displayVertex(v);
				System.out.println();
			}
		}
		for(int j=0;j<nVerts;j++)		//全部置为未访问
			vertexList[j].wasVisited = false;
	}
	
	public int noSuccessors(){	//使用邻接矩阵找到没有后继的顶点，有后继顶点返回行数，没有返回-1
		boolean isEdge;
		
		for(int row=0;row<nVerts;row++){//从第1行开始
			isEdge = false;
			for(int col=0;col<nVerts;col++){//如果某一行某一列为1，返回这个行的行数
				if(adjMat[row][col] > 0){
					isEdge = true;
					break;
				}
			}
			if(!isEdge)
				return row;
		}
		return -1;
	}
	
	public void moveRowUp(int row,int length){
		for(int col=0;col<length;col++)
			adjMat[row][col] = adjMat[row+1][col];
	}
	
	public void moveColLeft(int col,int length){
		for(int row=0;row<length;row++)
			adjMat[row][col] = adjMat[row][col+1];
	}
	
	public void deleteVertex(int delVert){
		if(delVert != nVerts-1){
			for(int j=delVert;j<nVerts-1;j++)//在数组中去掉这个顶点
				vertexList[j] = vertexList[j+1];
			for(int row=delVert;row<nVerts-1;row++)//在邻接矩阵中把删除的这一行下的所有行上移
				moveRowUp(row,nVerts);
			for(int col=delVert;col<nVerts-1;col++)//在邻接矩阵中把删除的这一列下的所有列左移
				moveColLeft(col,nVerts-1);
		}
		nVerts--;
	}
	
	public void topo(){	//拓扑排序，必须在无环的有向图中进行，必须在有向图中
		int orig_nVerts = nVerts;	//记录有多少个顶点
		
		while(nVerts > 0){
			int currentVertex = noSuccessors();
			if(currentVertex == -1){
				System.out.println("错误：图含有环！");
				return;
			}
			sortedArray[nVerts-1] = vertexList[currentVertex].label;
			deleteVertex(currentVertex);
		}
		System.out.println("拓扑排序结果：");
		for(int j=0;j<orig_nVerts;j++)
			System.out.println(sortedArray[j]);
		
	}
	
}