1 /** 2 * dfs(vertex v){ 3 * visit v; 4 * for each neighbor w of v 5 * if(w has not been visited){ 6 * dfs(w); 7 * } 8 * } 9 */10 /*深度优先搜索从顶点 v 开始*/11 public Tree dfs(int v){12 List searchOrders = new ArrayList ();//被搜索顶点的顺序13 int[] parent = new int[vertices.size()];//顶点的父结点14 for (int i = 0; i < parent.length; i++) {15 parent[i] = -1;16 }17 boolean[] isVisited = new boolean[vertices.size()];//跟踪已经访问过的结点18 dfs(v, parent, searchOrders, isVisited);19 20 return new Tree(v, parent, searchOrders);21 }22 private void dfs(int v, int[] parent, List searchOrders, boolean[] isVisited){23 searchOrders.add(v);24 isVisited[v] = true;25 26 for(int i : neighbors.get(v)){27 if(!isVisited[i]){28 parent[i] = v;29 dfs(v, parent, searchOrders, isVisited);30 }31 }32 }33 /**34 * 广度优先搜索35 * bfs(vertex v){36 * create an empty queue for storing vertices to be visited;37 * add v into the queue;38 * mark v visited39 * while the queue is not empty{40 * dequeue a vertex, say u, from the queue41 * add u into list for traversed vertices;42 * for each neighbor w of u43 * if w has nor been visited{44 * add w into the queue;45 * mark w visited;46 * }47 * }48 * }49 */50 public Tree bfs(int v){51 List searchOrders = new ArrayList ();52 int[] parent = new int[vertices.size()];53 for (int i = 0; i < parent.length; i++) {54 parent[i] = -1;55 }56 java.util.LinkedList queue = new java.util.LinkedList ();57 58 boolean[] isVisited = new boolean[vertices.size()];59 queue.offer(v);//进入队列60 isVisited[v] = true;61 62 while(!queue.isEmpty()){63 int u = queue.poll();//从队列中取出元素64 searchOrders.add(u);65 for(int w:neighbors.get(u)){66 if(!isVisited[w]){67 queue.offer(w);//进入队列68 parent[w] = u;69 isVisited[w] = true;//进入队列的结点就表示已经被访问过70 }71 }72 }73 return new Tree(v, parent, searchOrders);74 }