DepthFirstTraversal.java

packagecom.jwetherell.algorithms.graph;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;
importjava.util.Stack;

importcom.jwetherell.algorithms.data_structures.Graph;
importcom.jwetherell.algorithms.data_structures.Graph.Edge;
importcom.jwetherell.algorithms.data_structures.Graph.Vertex;

/**
 * Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and 
 * explores as far as possible along each branch before backtracking.
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Depth-first_search">Depth-First Search (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassDepthFirstTraversal {

@SuppressWarnings("unchecked")
publicstatic <TextendsComparable<T>> Graph.Vertex<T>[] depthFirstTraversal(Graph<T> graph, Graph.Vertex<T> source) {
// use for look-up via index
finalArrayList<Vertex<T>> vertices = newArrayList<Vertex<T>>();
vertices.addAll(graph.getVertices());

// used for look-up via vertex
finalintn = vertices.size();
finalMap<Vertex<T>,Integer> vertexToIndex = newHashMap<Vertex<T>,Integer>();
for (inti=0; i<n; i++) {
finalVertex<T> v = vertices.get(i);
vertexToIndex.put(v,i);
 }

// adjacency matrix
finalbyte[][] adj = newbyte[n][n];
for (inti=0; i<n; i++) {
finalVertex<T> v = vertices.get(i);
finalintidx = vertexToIndex.get(v);
finalbyte[] array = newbyte[n];
adj[idx] = array;
finalList<Edge<T>> edges = v.getEdges();
for (Edge<T> e : edges)
array[vertexToIndex.get(e.getToVertex())] = 1;
 }

// visited array
finalbyte[] visited = newbyte[n];
for (inti = 0; i < visited.length; i++)
visited[i] = -1;

// for holding results
finalGraph.Vertex<T>[] arr = newGraph.Vertex[n];

// start at the source
Vertex<T> element = source; 
intc = 0;
inti = vertexToIndex.get(element);
intk = 0;

visited[i] = 1;
arr[k] = element;
k++;

finalStack<Vertex<T>> stack = newStack<Vertex<T>>();
stack.push(source);
while (!stack.isEmpty()) { 
element = stack.peek();
c = vertexToIndex.get(element);
i = 0;
while (i < n) {
if (adj[c][i] == 1 && visited[i] == -1) {
finalVertex<T> v = vertices.get(i);
stack.push(v);
visited[i] = 1;

element = v;
c = vertexToIndex.get(element);
i = 0;

arr[k] = v;
k++;
continue;
 }
i++;
 }
stack.pop(); 
 }
returnarr;
 }

publicstaticint[] depthFirstTraversal(intn, byte[][] adjacencyMatrix, intsource) {
finalint[] visited = newint[n];
for (inti = 0; i < visited.length; i++)
visited[i] = -1;

intelement = source;
inti = source;
intarr[] = newint[n];
intk = 0;

visited[source] = 1;
arr[k] = element;
k++;

finalStack<Integer> stack = newStack<Integer>(); 
stack.push(source);
while (!stack.isEmpty()) { 
element = stack.peek();
i = 0; 
while (i < n) {
if (adjacencyMatrix[element][i] == 1 && visited[i] == -1) {
stack.push(i);
visited[i] = 1;

element = i;
i = 0;

arr[k] = element;
k++; 
continue;
 }
i++;
 }
stack.pop(); 
 }
returnarr;
 }
}