图的深度与广度优先遍历（BFS,DFS）（Java）

BFS基本就是按《算法导论》伪代码实现，DFS为通过栈实现，代码如下：

import java.awt.Color;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

public class BFSandDFStest {
	public static int time=0;//DFS用的，由于是结点共同的，所以在这设置了全局变量

	public static void main(String[] args) {
		Map<Vertex,List<Vertex>> G=new HashMap<>();//用map映射来完成图
		
		List<Vertex> aAdj=new LinkedList<>();
		List<Vertex> bAdj=new LinkedList<>();
		List<Vertex> cAdj=new LinkedList<>();
		List<Vertex> dAdj=new LinkedList<>();
		List<Vertex> eAdj=new LinkedList<>();
		
		Vertex A=new Vertex("A");
		Vertex B=new Vertex("B");
		Vertex C=new Vertex("C");
		Vertex D=new Vertex("D");
		Vertex E=new Vertex("E");
		
		aAdj.add(B);
		aAdj.add(D);
		bAdj.add(C);
		cAdj.add(D);
		cAdj.add(E);
		dAdj.add(C);
		dAdj.add(E);
		
		G.put(A, aAdj);
		G.put(B, bAdj);
		G.put(C, cAdj);
		G.put(D, dAdj);
		G.put(E, eAdj);
		
		BFS(G,A);//从A开始遍历
		DFS(G,A);
		
	}
	
	public static void BFS(Map<Vertex,List<Vertex>> G,Vertex A) {
		A.color=Color.GRAY;
		A.d=0;
		Queue<Vertex> Q=new LinkedList<>();//队列是接口
		Q.add(A);
		
		while(!Q.isEmpty()) {
			Vertex u=Q.poll();//取出一个节点
			for (Vertex v : G.get(u)) {//取出节点u的所有邻接节点
				if(v.color==Color.WHITE) {//只有未被发现才执行下面的语句
					v.color=Color.GRAY;
					v.d=u.d+1;
					v.p=u;
					Q.add(v);
				}
			}
			u.color=Color.BLACK;//u的所有邻接节点都变灰色了，u变黑
		}
		
		for (Vertex k : G.keySet()) {
			System.out.println("BFS后"+k+"点距离A为"+k.d);
		}
	}
	
	public static void DFS(Map<Vertex,List<Vertex>> G,Vertex A) {
		//由于BFS运行了，在这里初始化
		for (Vertex k : G.keySet()) {
			k.color=Color.WHITE;
			k.d=Integer.MAX_VALUE;
			k.p=null;
		}
		//从A开始
		DFSVisit(G,A);
		//以防有从A开始到不了的点，必须还有个循环
//		for (Vertex k : G.keySet()) {
//			//System.out.println(k);
//			if(k.color==Color.WHITE)
//				DFSVisit(G,k);
//		}
		//查看DFS后各点信息
		for (Vertex k : G.keySet()) {
			System.out.println(k.key+k.d+"/"+k.f);
		}
	}
	
	public static void DFSVisit(Map<Vertex,List<Vertex>> G,Vertex A) {
		Stack<Vertex> S=new Stack<>();
		S.push(A);
		A.d=++time;
		A.color=Color.GRAY;
		
		while(!S.isEmpty()) {
			Vertex u=S.peek();//只看不取,因为深度优先一轮一般不会变黑，不能取出来
			Vertex v=getAdj(G,u);//取处于栈顶的节点的一个非白邻点
				//可能没邻点或无非白邻点，有执行if后语句压栈，无执行else的描黑并出栈
			if(v!=null) {
				v.color=Color.GRAY;
				v.d=++time;
				v.p=u;
				S.push(v);
			}else {
				u.color=Color.BLACK;
				u.f=++time;
				S.pop();
			}
		}
	}
	
	public static Vertex getAdj(Map<Vertex,List<Vertex>> G,Vertex u) {
		for (Vertex v:G.get(u)) {
			if(v.color==Color.WHITE)  
				return v;
		}	
		return null;
	}
}


class Vertex{
	String key;
	Color color;
	int d;//BFS中代表与源的距离（边数），DFS中代表被发现时的时间戳
	int f;//DFS中代表变黑时的时间戳
	Vertex p;
	
	public  Vertex(String key) {
		this.key=key;
		color=Color.WHITE;
		d=Integer.MAX_VALUE;
		p=null;
		f=0;
	}
	
	public int hashCode() {//hashmap必须实现
		return key.hashCode();
	}
	
	public String toString() {
		return key;
	}
	
	public boolean equals(Object o) {//hashmap必须实现
		if(o==null||!(o instanceof Vertex) )
			return false;
		if(o==this)
			return true;
		return key.equals(((Vertex)o).key);
	}
}