java图的建立与遍历.

package test.table; public class GraphTraverse { public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("Generating the graph ... "); Graph g = new Graph(); g.addVertex('a'); g.addVertex('b'); g.addVertex('c'); g.addVertex('d'); g.addVertex('e'); g.addEdge(0,1); g.addEdge(0,2); g.addEdge(0,3); g.addEdge(1,4); g.addEdge(2,3); g.addEdge(2,4); System.out.println("The graph matrix is:"); g.showGraphyMatrix(); System.out.println("DFS of the graph:"); g.dfs(); System.out.println("End"); System.out.println("BFS of the graph:"); g.bfs(); System.out.println("End"); System.out.println("DFS of the graph by recursion:"); g.dfsTraverse(); System.out.println("End"); } } //用于实现深度优先搜索的栈类 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 peek(){ return st[top]; } public boolean isEmpty(){ return top==-1; } } //用于实现广度优先搜索的队列类 class Queue { private final int SIZE=20; private int[] queArray; private int front; private int rear; public Queue(){ queArray=new int[SIZE]; front=0; rear=-1; } public void insert(int j){ if(rear==SIZE-1) rear=-1; queArray[++rear]=j; } public int remove(){ int temp=queArray[front++]; if(front==SIZE) front=0; return temp; } public boolean isEmpty(){ return ((rear+1==front)||(front+SIZE-1==rear)); } } //顶点类 class Vertex { public char label; public boolean wasVisited; public Vertex(char lab){ label=lab; wasVisited=false; } } //图类 class Graph { private final int MAX_VERTS=20; private Vertex vertexList[]; private int adjMat[][]; private int nVerts; private StackX theStack; private Queue theQueue; 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; } } theStack=new StackX(); theQueue=new Queue(); } //增加一个顶点 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 void showGraphyMatrix(){ for(int i=0;i<5;i++){ for(int j=0;j<5;j++) System.out.print(adjMat[i][j]); System.out.println(); } } //得到与v顶点邻接且未访问过的顶点标号 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; } //深度优先搜索使用栈 public void dfs(){ vertexList[0].wasVisited=true; displayVertex(0); theStack.push(0); while(!theStack.isEmpty()){ 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