1: // @author Frank M. Carrano, Timothy M. Henry
2: // @version 5.0
3: public QueueInterface<T> getBreadthFirstTraversal(T origin)
4: {
5: resetVertices();
6: QueueInterface<T> traversalOrder = new LinkedQueue<>();
7: QueueInterface<VertexInterface<T>> vertexQueue = new LinkedQueue<>();
8:
9: VertexInterface<T> originVertex = vertices.getValue(origin);
10: originVertex.visit();
11: traversalOrder.enqueue(origin); // Enqueue vertex label
12: vertexQueue.enqueue(originVertex); // Enqueue vertex
14: while (!vertexQueue.isEmpty())
15: {
16: VertexInterface<T> frontVertex = vertexQueue.dequeue();
17: Iterator<VertexInterface<T>> neighbors = frontVertex.getNeighborIterator();
19: while (neighbors.hasNext())
20: {
21: VertexInterface<T> nextNeighbor = neighbors.next();
22: if (!nextNeighbor.isVisited())
23: {
24: nextNeighbor.visit();
25: traversalOrder.enqueue(nextNeighbor.getLabel());
26: vertexQueue.enqueue(nextNeighbor);
27: } // end if
28: } // end while
29: } // end while
31: return traversalOrder;
32: } // end getBreadthFirstTraversal