图的遍历代码,Java代码库,德仔网

代码语言

代码分类

【Java】图的遍历

作者:茶壶 / 发布于2015/6/29/ 741


	/**
	* 图
	* @author DBJ(dubenju@126.com)
	*/
	public class DefaultGraph implements Graph {
	
	 /** 顶点集 */
	 private ArrayList<Vertex> vertexes;
	 /** 邻接表 */
	 private ArrayList<LinkedList<Edge>> adjacencyList;
	 private int edgeSize;
	
	 /**
	 * 遍历
	 */
	
	 /**
	 * 深度优先遍历(DFS)
	 */
	 public void depthFirstTraversal(GraphVisitor visitor) {
	 // reset Visited
	 initVisit();
	 for(int i = 0; i < this.vertexes.size(); i ++) {
	 Vertex vertex = this.vertexes.get(i);
	 if(vertex.isVisited() == false) {
	 do_DFS(vertex, visitor);
	 }
	 }
	 }
	
	 /**
	 * 深度优先遍历x
	 * @param v 顶点
	 * @param visitor
	 */
	 private final void do_DFS(Vertex v, GraphVisitor visitor) {
	 // first visit this vertex
	 visitor.visit(this, v);
	 v.setVisit(true);
	
	 // for each edge from this vertex, we do one time and this for loop is very classical in all graph algorithms
	 for(Edge e = firstEdge(v); isEdge(e); e = e.getNextEdge()) {
	 if(e.getTo().isVisited() == false) {
	 do_DFS(e.getTo(), visitor);
	 }
	 }
	 }
	
	 /**
	 * 广度优先遍历(BFS)
	 */
	 public void breathFirstTraversal(GraphVisitor visitor) {
	 // reset Visited
	 initVisit();
	 for(int i = 0; i < this.vertexes.size(); i ++) {
	 Vertex vertex = this.vertexes.get(i);
	 if(vertex.isVisited() == false) {
	 do_BFS(vertex, visitor);
	 }
	 }
	 }
	
	 /**
	 * 广度优先遍历x
	 * @param v 顶点
	 * @param visitor
	 */
	 private void do_BFS(Vertex v, GraphVisitor visitor) {
	 // BFS will use an queue to keep the unvisited vertexes. we can also just use java.util.LinkedList
	 LinkedList<Vertex> queue = new LinkedList<Vertex>();
	 queue.add(v);
	 while(!queue.isEmpty()) {
	 Vertex fromV = queue.poll();
	 if (fromV.isVisited() == false) {
	 visitor.visit(this, fromV);
	 fromV.setVisit(true);
	 for(Edge e = firstEdge(fromV); isEdge(e); e = e.getNextEdge()) {
	 Vertex toV = e.getTo();
	 if(toV.isVisited() == false) {
	 queue.add(toV);
	 }
	 }
	 }
	 }
	 }
	 下略
	}

试试其它关键字

　图　　遍历　

同语言下

可能有用的

茶壶贡献的其它代码(9)