Depth-First Search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node of an arbitrary node and explores as far as possible in the branch before backtracking.
Properties of Depth-first Search :
- The time complexity of DFS to traverse an entire graph takes time O(|V| + |E| ) where V refers to vertices and E for Edges in a graph.
- This traversal algorithm takes a total of O(|V|) space for a complete traversal.
- DFS internally uses a stack to find the closest path.
- In terms of speed, DFS is better compared to Breadth-first search.
How DFS Works?
Depth-first Traversal (or Search) for a graph is similar to traversal in a tree and the approach here is to start from the root node and move to its adjacent unvisited nodes, when there's no adjacent node, we backtrack to the parent node. This avoids visiting of processed node twice in a traversal.
In the above figure, it is an example of a directed graph with the vertices [A, B, C, D, E] with the edges:
- A to B and A to C
- B to D
- C to E
- D to E
- Start by iterating over the array list and pass each of the vertexes to the helper function.
- The helper function with vertex parameter marks the visited array corresponding to that vertex as true.
- Traverse each of the adjacent vertexes and mark them as visited.
Algorithm:
- Create a multidimensional array list of integer types.
- Add the vertices with their respective edges to the list.
- Create a boolean array to keep track of visited vertices.
- Create a stack of Integer type and push the root vertex.
- Print the current vertex and mark it as visited.
- Iterate through the adjacent unvisited vertices present in the list till the stack is empty.
Implementation of Depth-first Search in java:
The following function requires an index of node and array as parameters.
class DFS {
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
int vertex = 5;
for (int i = 0; i < vertex; i++) {
ArrayList<Integer> l = new ArrayList<Integer>();
list.add(l);
}
// Here as from the above graph consider A,B,C,D,E as 0,1,2,3,4
// These are following edges: 0->1 & 0->2
// 1->3 & 2->4 & 3->4
list.get(0).add(1);
list.get(0).add(2);
list.get(1).add(3);
list.get(2).add(4);
list.get(3).add(4);
// set every vertex value as unvisited
boolean[] visited = new boolean[vertex];
for (int i = 0; i < vertex; i++) {
visited[i] = false;
}
// pass the parameters to DFS function
DFS(list, visited, vertex);
}
public static void DFS(ArrayList<ArrayList<Integer>> list, boolean visited[], int vertex) {
Stack<Integer> s = new Stack<>();
s.push(0);
while (!s.empty()) {
int temp = s.pop();
System.out.print(temp + " ");
visited[temp] = true;
for (int i = 0; i < list.get(temp).size(); i++) {
if (!visited[list.get(temp).get(i)]) {
s.push(list.get(temp).get(i));
}
}
}
}
}
This function prints the vertex by visiting every vertex in the graph.
I hope you guys liked this article and here are some articles you may like:
0 Comments