## Given problem

Assuming that we have a graph that is described in a below image.

``````   1
/   \
2     3
|  \  |
4 -- 5
\  /
6
``````

## Definition of Graph

`````` public class ALGraph {
private ArrayList<List<Node>> graphs;

public ALGraph(int capacity) {
this.graphs = new ArrayList<>(capacity);
for (int i = 0; i < capacity; ++i) {
}
}

public List<Node> getNodesWith(int vertex) {
return this.graphs.get(vertex);
}

/**
* an edge from u vertex to v vertex and vice versa
*
* @param u
* @param v
*/
public void addEdge(Node u, Node v) {
Objects.requireNonNull(u);
Objects.requireNonNull(v);

}

public void display() {
int len = this.graphs.size();
for (int i = 1; i < len; ++i) {
List<Node> nodes = this.graphs.get(i);

System.out.println("Vertex " + i + " connect with: ");
for (Node node : nodes) {
System.out.print(" --> " + node.value + " ");
}

System.out.println();
}
}
}

public class Demo {
public static void main(String[] args) {
int capacity = 7;
ALGraph graph = initALGraph(capacity);
boolean[] visited = new boolean[capacity];

dfs(graph, visited, new Node(1));
}

public static ALGraph initALGraph(int capacity) {
ALGraph graph = new ALGraph(capacity);

return graph;
}
}
``````

`````` public class AMGraph {
private int[][] graph;
private int capacity;

public AMGraph(int capacity) {
this.capacity = capacity;
this.graph = new int[capacity][capacity];
}

public int getCapacity() {
return this.capacity;
}

public boolean isAnEdge(int u, int v) {
return this.graph[u][v] == 1;
}

public void addEdge(int u, int v) {
this.graph[u][v] = 1;
this.graph[v][u] = 1;
}

public void display() {
for (int i = 1; i < this.capacity; ++i) {
System.out.println("Vertex " + i + " connect with: ");

for (int j = 1; j < this.capacity; ++j) {
if (this.graph[i][j] == 1) {
System.out.print(" --> " + j + " ");
}
}

System.out.println();
}
}
}

public class Demo {
public static void main(String[] args) {
int capacity = 7;
AMGraph graph = new AMGraph(capacity);
boolean[] visited = new boolean[capacity];

dfs(graph, visited, 1);
}

public void initAMGraph(int capacity) {
AMGraph graph = new AMGraph(capacity);

return graph;
}
}
``````

## Using recursive version

`````` /**
* Using recursive version
*
* Result: 1 --> 2 --> 4 --> 5 --> 3 --> 6
*
* @param graph
* @param visited
* @param node
*/
public static void dfs(ALGraph graph, boolean[] visited, Node node) {
Objects.requireNonNull(node);

if (visited[node.value]) {
return;
}

visited[node.value] = true;
System.out.print("" + node.value + " --> ");

List<Node> nodes = graph.getNodesWith(node.value);
for (Node tmpNode : nodes) {
dfs(graph, visited, tmpNode);
}
}
``````

The dfs in the recursive version is as same as the source code in Preorder traversal in Binary Tree.

Using a boolean array - visited to mark nodes that is iterated. It makes us do not touch it in twice times.

`````` public static void dfs(AMGraph graph, boolean[] visited, int node) {
System.out.print("" + node + " --> ");
visited[node] = true;

for (int i = 1; i < graph.getCapacity(); ++i) {
if (graph.isAnEdge(node, i) && !visited[i]) {
dfs(graph, visited, i);
}
}
}
``````

## Using iterative version

`````` public static void dfsUnRecursive(ALGraph graph, boolean[] visited) {
Stack<Node> stkNodes = new Stack<>();
stkNodes.push(new Node(1));

while (!stkNodes.isEmpty()) {
Node topNode = stkNodes.pop();

// prepare for the node iterate in twice times
if (!visited[topNode.value]) {
visited[topNode.value] = true;
System.out.print("" + topNode.value + " --> ");
}

List<Node> childNodes = graph.getNodesWith(topNode.value);
for (Node tmpNode : childNodes) {
if (!visited[tmpNode.value]) {
stkNodes.push(tmpNode);
}
}
}
}
``````

## Applications of DFS

• Minimum spanning tree

• Detecting cycle in the graph

• Find path between the two vertices

• Topological sorting

• Check bipartite graph

• Find the strongly connected components

• Maze solution