图的深度优先搜索DFS和广度优先搜索BFS 笔记

（下图皆来自：java数据结构和算法（第二版））

一、深度优先搜索DFS：

package com.hqy.graph;

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 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;
	
	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();
	}
	
	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 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<nVerts;j++){
			vertexList[j].wasVisited=false;
		}
	}
	
	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 class DFSApp {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Graph theGraph=new Graph();
		theGraph.addVertex('A');
		theGraph.addVertex('B');
		theGraph.addVertex('C');
		theGraph.addVertex('D');
		theGraph.addVertex('E');
		theGraph.addVertex('F');
		
		theGraph.addEdge(0, 1);
		theGraph.addEdge(1, 5);
		theGraph.addEdge(0, 5);
		theGraph.addEdge(3, 4);
		theGraph.addEdge(2, 3);
		theGraph.addEdge(2, 5);
		theGraph.addEdge(4, 5);
		
		System.out.print("visits:");
		theGraph.dfs();
		System.out.println();	
		
	}
pa