GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1032

194
195 @Override /** Starting bfs search from vertex v */
196 /** To be discussed in Section 28.9 */
197 public Tree bfs( int v) {
198 List<Integer> searchOrder = new ArrayList<>();
199 int [] parent = new int [vertices.size()];
200 for ( int i = 0 ; i < parent.length; i++)
201 parent[i] = -1 ; // Initialize parent[i] to -1
202
203 java.util.LinkedList<Integer> queue =
204 new java.util.LinkedList<>(); // list used as a queue
205 boolean [] isVisited = new boolean [vertices.size()];
206 queue.offer(v); // Enqueue v
207 isVisited[v] = true ; // Mark it visited
208
209 while (!queue.isEmpty()) {
210 int u = queue.poll(); // Dequeue to u
211 searchOrder.add(u); // u searched
212 for (Edge e: neighbors.get(u)) {
213 if (!isVisited[e.v]) {
214 queue.offer(e.v); // Enqueue w
215 parent[e.v] = u; // The parent of w is u
216 isVisited[e.v] = true ; // Mark it visited
217 }
218 }
219 }
220
221

bfs method

return new Tree(v, parent, searchOrder);

222 }
223
224

/** Tree inner class inside the AbstractGraph class */

225 /** To be discussed in Section 28.6 */

226 public class Tree {

Tree inner class

227 private int root; // The root of the tree

228 private int [] parent; // Store the parent of each vertex

229 private List<Integer> searchOrder; // Store the search order

230
231

/** Construct a tree with root, parent, and searchOrder */

232 public Tree( int root, int [] parent, List<Integer> searchOrder) {

233 this .root = root;

234 this .parent = parent;

235 this .searchOrder = searchOrder;

236 }
237
238

/** Return the root of the tree */

239 public int getRoot() {

240 return root;

241 }
242
243 /** Return the parent of vertex v */

244 public int getParent( int v) {

245 return parent[v];

246 }
247
248

/** Return an array representing search order */

249 public List<Integer> getSearchOrder() {

250 return searchOrder;

251 }
252
253 /** Return number of vertices found */

254 public int getNumberOfVerticesFound() {