Graph and tree nodes can be traversed using the backtracking technique. Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. DFS takes less memory compare than Breadth-first search and not necessary to store all of the child pointers at each level.
DFS technique used in web-crawling, Finding connected components, Topological sorting, Finding the bridges of a graph, Finding strongly connected components, Solving puzzles with only one solution, such as mazes, maze generation may use a randomized depth-first search, Finding connectivity in graphs.
source Code
package com.dsacode.Algorithm.backtracking; import java.util.Stack; class Vertex{ public char label; public boolean wasVisited; public Vertex(char lab){ label = lab; wasVisited = false; } } public class DepthFirstSearch { private final int MAX_VERTS = 20; private Vertex vertexList[]; private int adjMat[][]; private int nVerts; private Stack < Integer > theStack; public DepthFirstSearch() { vertexList = new Vertex[MAX_VERTS]; adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int y = 0; y < MAX_VERTS; y++) for(int x = 0; x < MAX_VERTS; x++) adjMat[x][y] = 0; theStack = new Stack < Integer >(); } public void addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); } public void addEdge(int start, int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; } public void displayVertex(int v) { System.out.print(vertexList[v].label+"->"); } public void dfs() { vertexList[0].wasVisited = true; displayVertex(0); theStack.push(0); while( !theStack.isEmpty() ) { int v = getAdjUnvisitedVertex( theStack.peek() ); if(v == -1) theStack.pop(); else { vertexList[v].wasVisited = true; displayVertex(v); theStack.push(v); } } for(int j=0; j < nVerts; j++) vertexList[j].wasVisited = false; } public int getAdjUnvisitedVertex(Integer v) { for(int j=0; j < nVerts; j++) if(adjMat[v][j]==1 && vertexList[j].wasVisited==false) return j; return -1; } public static void main(String[] args) { DepthFirstSearch theGraph = new DepthFirstSearch(); theGraph.addVertex('A'); theGraph.addVertex('B'); theGraph.addVertex('C'); theGraph.addVertex('D'); theGraph.addVertex('E'); theGraph.addEdge(0, 1); theGraph.addEdge(1, 2); theGraph.addEdge(0, 3); theGraph.addEdge(3, 4); System.out.print("Visits from source to destination using DFS: "); theGraph.dfs(); System.out.println(); } }
Output
Visits from source to destination using DFS: A->B->C->D->E
Algorithm Explanation
![]() | Use a stack to store vertex. |
![]() | Graphs may contain cycles, to avoid processing a node more than once use a Boolean visited array. |
![]() | Pop each element from the stack. peek the element from the stack and find all vertexes. |
![]() | If v is -1 pop the stack. otherwise, mark as visited node and push to the stack. Repeat the above steps for all the vertex. |