package com.homework;
/** 
 * 定义栈类 
 */
class StackX{
 private final int size = 20;
 private int[] st;
 private int top;
 //初始化栈 
 public StackX(){
  st = new int[size];
  top = -1;
 }
 //进栈 
 public void push(int j){
  st[++top] = j;
 }
 //出栈 
 public int pop(){
  return st[top--];
 }
 //返回栈顶元素 
 public int peak(){
  return st[top];
 }
 //判断栈是否为空 
 public Boolean isEmpty(){
  return (top==-1);
 }
}
/** 
 * 定义图中的节点类 
 * @author Administrator 
 * 
 */
class Vertex{
 public char label;
 public Boolean wasVisited;
 public Vertex(char lab){
  label = lab;
  wasVisited = false;
 }
}
/** 
 * 定义图类 
 * @author Administrator 
 * 
 */
class Graph{
 private final int num = 20;
 private Vertex vertexList[];
 //图中节点数组 
 private int adjMat[][];
 //节点矩阵 
 private int nVerts;
 //当前节点数 
 private StackX theStack;
 //定义一个栈 
 //初始化图的结构 
 public Graph(){
  vertexList = new Vertex[num];
  adjMat = new int[num][num];
  nVerts = 0;
  for (int i=0; i<num; i++){
   for (int j=0; j<num; j++) 
           adjMat[i][j] = 0;
  }
 }
 //添加节点 
 public void addVertex(char lab){
  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){
  for (int j=0; j<nVerts; j++){
   if(adjMat[v][j]==1 && vertexList[j].wasVisited==false) 
           return j;
  }
  return -1;
 }
 //深度优先遍历（DFS） 
 public void dfs(){
  vertexList[0].wasVisited=true;
  displayVertex(0);
  theStack= new StackX();
  theStack.push(0);
  while(!theStack.isEmpty()){
   int v = getAdjUnvisitedVertex(theStack.peak());
   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 class GraphConnect {
 public static void main(String[] args){
  {
   Graph theGraph = new Graph();
   theGraph.addVertex('A');
   theGraph.addVertex('B');
   theGraph.addVertex('C');
   theGraph.addVertex('D');
   theGraph.addVertex('E');
   theGraph.addEdge(0, 1);
   //AB 
   theGraph.addEdge(1, 2);
   //BC 
   theGraph.addEdge(0, 3);
   //AD 
   theGraph.addEdge(3, 4);
   //DE 
   theGraph.addEdge(2, 4);
   //CE 
   System.out.print("The order visited:");
   theGraph.dfs();
   System.out.println();
  }
 }
}

The order visited:ABCED