黑马程序员技术交流社区

标题: 图的遍历 [打印本页]
作者: fantianfei    时间: 2015-7-1 10:07
标题: 图的遍历
分享一个，望版主不要再无缘无故删帖：
  1. /**
  2. * 图
  3. * @author DBJ(dubenju@126.com)
  4. */
  5. public class DefaultGraph implements Graph {

  7.     /** 顶点集  */
  8.     private ArrayList<Vertex> vertexes;
  9.     /** 邻接表  */
  10.     private ArrayList<LinkedList<Edge>> adjacencyList;
  11.     private int edgeSize;

  13.     /**
  14.      * 遍历
  15.      */

  17.     /**
  18.      * 深度优先遍历(DFS)
  19.      */
  20.     public void depthFirstTraversal(GraphVisitor visitor) {
  21.         // reset Visited
  22.         initVisit();
  23.         for(int i = 0; i < this.vertexes.size(); i ++) {
  24.             Vertex vertex = this.vertexes.get(i);
  25.             if(vertex.isVisited() == false) {
  26.                 do_DFS(vertex, visitor);
  27.             }
  28.         }
  29.     }

  31.     /**
  32.      * 深度优先遍历x
  33.      * @param v 顶点
  34.      * @param visitor
  35.      */
  36.     private final void do_DFS(Vertex v, GraphVisitor visitor) {
  37.         // first visit this vertex
  38.         visitor.visit(this, v);
  39.         v.setVisit(true);

  41.         // for each edge from this vertex, we do one time and this for loop is very classical in all graph algorithms
  42.         for(Edge e = firstEdge(v); isEdge(e); e = e.getNextEdge()) {
  43.             if(e.getTo().isVisited() == false) {
  44.                 do_DFS(e.getTo(), visitor);
  45.             }
  46.         }
  47.     }

  49.     /**
  50.      * 广度优先遍历(BFS)
  51.      */
  52.     public void breathFirstTraversal(GraphVisitor visitor) {
  53.         // reset Visited
  54.         initVisit();
  55.         for(int i = 0; i < this.vertexes.size(); i ++) {
  56.             Vertex vertex = this.vertexes.get(i);
  57.             if(vertex.isVisited() == false) {
  58.                 do_BFS(vertex, visitor);
  59.             }
  60.         }
  61.     }

  63.     /**
  64.      * 广度优先遍历x
  65.      * @param v 顶点
  66.      * @param visitor
  67.      */
  68.     private void do_BFS(Vertex v, GraphVisitor visitor) {
  69.         // BFS will use an queue to keep the unvisited vertexes. we can also just use java.util.LinkedList
  70.         LinkedList<Vertex> queue = new LinkedList<Vertex>();
  71.         queue.add(v);
  72.         while(!queue.isEmpty()) {
  73.             Vertex fromV = queue.poll();
  74.             if (fromV.isVisited() == false) {
  75.                 visitor.visit(this, fromV);
  76.                 fromV.setVisit(true);
  77.                 for(Edge e = firstEdge(fromV); isEdge(e); e = e.getNextEdge()) {
  78.                     Vertex toV = e.getTo();
  79.                     if(toV.isVisited() == false) {
  80.                         queue.add(toV);
  81.                     }
  82.                 }
  83.             }
  84.         }
  85.     }
  86.    
  87. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2