Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Non-Recursive DFS implementation by using a Stack
package graph.search.dfs;
import graph.entity.Vertex;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;
/**
* Non-Recursive DFS implementation by using an exclusive stack. Moreover, we have to keep <bold>iterators</bold> of adjacency lists of each vertex,
* so that iterators will continue to iterate from their final position.
*
*/
public class DFSNonrecursive {
public static int time = 0;
public void dfsNonrecursive(ArrayList<Vertex> graph, Vertex source) {
if (graph == null || source == null) {
throw new IllegalArgumentException("Parameters can not be null");
}
initVertices(graph, source);
HashMap<String, Iterator<Vertex>> iterMap = new HashMap<>();
// add iterators into a hashmap with label of each vertex as key
for (Vertex vertex : graph) {
iterMap.put(vertex.getLabel(), vertex.getAdjList().iterator());
}
Stack<Vertex> stack = new Stack<>();
time = time + 1;
source.setExplored(true);
source.setDiscoveryTime(time);
stack.push(source);
while (!stack.isEmpty()) {
Vertex peek = stack.peek();
// get the iterator of peek so that iterator will continue
// from its last position.
Iterator<Vertex> iterator = iterMap.get(peek.getLabel());
if (iterator.hasNext()) {
Vertex adjVertex = iterator.next();
if (!adjVertex.isExplored()) {
time = time + 1;
adjVertex.setDiscoveryTime(time);
adjVertex.setExplored(true);
stack.push(adjVertex);
}
} else {
time = time + 1;
peek.setFinishedTime(time);
stack.pop();
}
}
}
/**
* Make all vertices undiscovered
*
* @param graph
*/
private void initVertices(ArrayList<Vertex> graph, Vertex source) {
for (Vertex vertex : graph) {
if (vertex != source)
vertex.setExplored(false);
}
}
}
package graph.search.dfs;
import static org.junit.Assert.assertEquals;
import graph.entity.Vertex;
import java.util.ArrayList;
import java.util.Arrays;
import org.junit.Before;
import org.junit.Test;
/**
* Non-Recursive version of DFS.
*
* @author buraktas
*
*/
public class DFSNonRecursiveTest {
private DFSNonrecursive testClass;
private ArrayList<Vertex> graph;
@Before
public void setUp() {
testClass = new DFSNonrecursive();
graph = new ArrayList<>();
}
@Test(expected = IllegalArgumentException.class)
public void testNullGraph() {
Vertex q = new Vertex("q");
testClass.dfsNonrecursive(null, q);
}
@Test(expected = IllegalArgumentException.class)
public void testNullSource() {
testClass.dfsNonrecursive(graph, null);
}
@Test
public void testDFS() {
initGraph();
testClass.dfsNonrecursive(graph, graph.get(0));
assertEquals(10, graph.get(9).getDiscoveryTime());
assertEquals(14, graph.get(8).getFinishedTime());
for (Vertex vertex : graph) {
System.out.println("Vertex : "
+ vertex.getLabel()
+ " Dis. Time : "
+ vertex.getDiscoveryTime()
+ " Fin. Time : "
+ vertex.getFinishedTime());
}
}
private void initGraph() {
Vertex q = new Vertex("q");
Vertex s = new Vertex("s");
Vertex v = new Vertex("v");
Vertex w = new Vertex("w");
Vertex t = new Vertex("t");
Vertex x = new Vertex("x");
Vertex y = new Vertex("y");
Vertex z = new Vertex("z");
Vertex r = new Vertex("r");
Vertex u = new Vertex("u");
q.setAdjList(new ArrayList<>(Arrays.asList(s, t, w)));
s.setAdjList(new ArrayList<>(Arrays.asList(v)));
v.setAdjList(new ArrayList<>(Arrays.asList(w)));
w.setAdjList(new ArrayList<>(Arrays.asList(s)));
t.setAdjList(new ArrayList<>(Arrays.asList(x, y)));
x.setAdjList(new ArrayList<>(Arrays.asList(z)));
z.setAdjList(new ArrayList<>(Arrays.asList(x)));
y.setAdjList(new ArrayList<>(Arrays.asList(q)));
r.setAdjList(new ArrayList<>(Arrays.asList(u, y)));
u.setAdjList(new ArrayList<>(Arrays.asList(y)));
graph.add(q);
graph.add(r);
graph.add(s);
graph.add(t);
graph.add(u);
graph.add(v);
graph.add(w);
graph.add(x);
graph.add(y);
graph.add(z);
}
}
package graph.entity;
import java.util.ArrayList;
public class Vertex {
private boolean explored;
private ArrayList<Vertex> adjList;
private final String label;
private int discoveryTime;
private int finishedTime;
public int getDiscoveryTime() {
return discoveryTime;
}
public void setDiscoveryTime(int discoveryTime) {
this.discoveryTime = discoveryTime;
}
public int getFinishedTime() {
return finishedTime;
}
public void setFinishedTime(int finishedTime) {
this.finishedTime = finishedTime;
}
public Vertex(String label) {
this.label = label;
}
public boolean isExplored() {
return explored;
}
public void setExplored(boolean explored) {
this.explored = explored;
}
public ArrayList<Vertex> getAdjList() {
return adjList;
}
public void setAdjList(ArrayList<Vertex> adjList) {
this.adjList = adjList;
}
public String getLabel() {
return label;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment