// Recursive depth-first search public int[] recursiveDepthFirstTraversal(int currentVertex, boolean [] visited, int [] dFTTree) { System.out.println(names[currentVertex]); // Get the indices of the neighbors of the current vertex int[] neighbors = getNeighbors(currentVertex); // Scan the neighbors of the current vertex, looking // for an unvisited neighbor int j = 0; while (j < neighbors.length) { // If an unvisited neighbor has been found, // mark it visited, make the current vertex its parent, // and call depth-first search with that neighbor as the // source if(!visited[neighbors[j]]) { visited[neighbors[j]] = true; dFTTree[neighbors[j]] = currentVertex; recursiveDepthFirstTraversal(neighbors[j], visited, dFTTree); // Re-output the current vertex for tracing purposes System.out.println(names[currentVertex]); } j++; // scan the next vertex } // We've visited all our children, so return the tree. return dFTTree; } // This function does initialization needed for depth-first search. It also // calls recursive depth first search separately for each connected component of // the graph. public int[] rDepthFirstTraversal(String source) { // Getting the index of the source vertex and // checking if the vertex really exists int sourceIndex = getIndex(source); if(sourceIndex == -1) { System.out.print("In rDepthFirstTraversal: vertex "); System.out.print(source); System.out.println(" is missing."); return null; } // Defining and initializing the visited array boolean[] visited = new boolean[numVertices]; for(int j = 0; j < numVertices; j++) visited[j] = false; // Defining and initializing the depth first traversal tree int[] dFTTree = new int[numVertices]; for(int j = 0; j < numVertices; j++) dFTTree[j] = -1; boolean more; do { visited[sourceIndex] = true; recursiveDepthFirstTraversal(sourceIndex, visited, dFTTree); // Determine if there are more unvisited vertices // by scanning the visited array and looking for the // first unvisited vertex more = false; int j = 0; while(j < numVertices && !more) { if(!visited[j]) { more = true; sourceIndex = j; } j++; } } while(more); return dFTTree; } // end of function