Could you please help me? Algorithm getDepthFirstTraversal(originVertex) travers

Question

Could you please help me?

Algorithm getDepthFirstTraversal(originVertex) traversalOrder = a new stack to hold vertices as they are visited Mark originVertex as visited traversalOrder.enqueue(originVertex) vertexStack. push (originVertex) while (vertexStack.isEmpty()) topVertex = vertexStack.peek() if (topvertex has an unvisited neighbor) nextNeighbor = next unvisited neighbor of topVertex Mark nextNeighbor as visited traversalOrder.enqueue(nextNeighbor) vertexStack.push(nextNeighbor) else vertexStack.pop() return traversalOrder

Explanation / Answer

import java.util.*; import java.util.concurrent.LinkedBlockingDeque; import java.util.concurrent.LinkedBlockingQueue; /** * A class that implements the ADT directed graph. * * @author Frank M. Carrano * @version 04/11/2015 * @modifiedBy Anna Bieszczad */ public class DirectedGraph implements GraphInterface { private Map vertices; private int edgeCount; public DirectedGraph() { this.vertices = new TreeMap(); this.edgeCount = 0; } // end default constructor public boolean addVertex(T vertexLabel) { VertexInterface isDuplicate = this.vertices.put(vertexLabel, new Vertex(vertexLabel)); return isDuplicate == null; // was add to dictionary successful? } // end addVertex public boolean addEdge(T begin, T end, double edgeWeight) { boolean result = false; VertexInterface beginVertex = this.vertices.get(begin); VertexInterface endVertex = this.vertices.get(end); if ((beginVertex != null) && (endVertex != null)) result = beginVertex.connect(endVertex, edgeWeight); if (result) this.edgeCount++; return result; } // end addEdge public boolean addEdge(T begin, T end) { return addEdge(begin, end, 0); } // end addEdge public boolean hasEdge(T begin, T end) { boolean found = false; VertexInterface beginVertex = this.vertices.get(begin); VertexInterface endVertex = this.vertices.get(end); if ((beginVertex != null) && (endVertex != null)) { Iterator neighbors = beginVertex.getNeighborIterator(); while (!found && neighbors.hasNext()) { VertexInterface nextNeighbor = neighbors.next(); if (endVertex.equals(nextNeighbor)) found = true; } } return found; } // end hasEdge public boolean isEmpty() { return this.vertices.isEmpty(); } // end isEmpty public void clear() { this.vertices.clear(); this.edgeCount = 0; } // end clear public int getNumberOfVertices() { return this.vertices.size(); } // end getNumberOfVertices public int getNumberOfEdges() { return this.edgeCount; } // end getNumberOfEdges protected void resetVertices() { Collection values = this.vertices.values(); Iterator vertexIterator = values.iterator(); while (vertexIterator.hasNext()) { VertexInterface nextVertex = vertexIterator.next(); nextVertex.unvisit(); nextVertex.setCost(0); nextVertex.setPredecessor(null); } } // end resetVertices public Queue getBreadthFirstTraversal(T origin) { resetVertices(); Queue traversalOrder = new LinkedBlockingQueue(); Queue vertexQueue = new LinkedBlockingQueue(); VertexInterface originVertex = this.vertices.get(origin); originVertex.visit(); traversalOrder.offer(origin); // enqueue vertex label vertexQueue.offer(originVertex); // enqueue vertex while (!vertexQueue.isEmpty()) { VertexInterface frontVertex = vertexQueue.poll(); Iterator neighbors = frontVertex.getNeighborIterator(); while (neighbors.hasNext()) { VertexInterface nextNeighbor = neighbors.next(); if (!nextNeighbor.isVisited()) { nextNeighbor.visit(); traversalOrder.offer(nextNeighbor.getLabel()); vertexQueue.offer(nextNeighbor); } } } return traversalOrder; } // end getBreadthFirstTraversal /** * traversalOrder = a new queue for the resulting traversal order * vertexStack = a new stack to hold vertices as they are visited * * Mark originVertex as visited * traversalOrder.enqueue(originVertex) * vertexStack.push(originVertex) * * while(!vertexStack.isEmpty()) * { * topVertex = vertexStack.peek() * if (topVertex has an unvisited neighbor) * { * nextNeighbor = next unvisited neighbor of topVertex * Mark nextNeighbor as visited * traversalOrder.enqueue(nextNeighbor) * vertexStack.push(nextNeighbor) * } * else // all neighbors are visited * { * vertexStack.pop() * } * } * return traversalOrder * @param origin an object that labels the origin vertex of the * traversal * * * @return traversalOrder */ public Queue getDepthFirstTraversal(T origin) //

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.