depth-first search - dfs

note

• Strategy: expand a deepest node first
• Implementation: fringe is a LIFO stack
• Properties:
  • Nodes DFS expand?
    • Some left prefix of the tree
    • Could process the whole tree
    • If m is finite, takes time $$\begin{gathered} (O(b^m) \\ ) \end{gathered}$$
  • Time complexity: $$\begin{gathered} (O(b^m) \\ ) \end{gathered}$$
    • b: branching factor (the average number of successors per state)
    • m: maximum depth
    • search has to explore the entire tree before finding a solution or concluding that none exists.
  • Space complexity: $$\begin{gathered} (O(bm) \\ ) \end{gathered}$$
    • search stores nodes & their siblings along path from root → current node, with at most length is m
    • at most number of siblings each level is b
  • Complete: finite only if we prevent cycles
  • Optimal: no. find the leftmost solution regardless of depth or cost
• 

when to use

• detect cycles in a tree

implementation

// Java program to print DFS traversal
// from a given graph
import java.io.*;
import java.util.*;
 
// This class represents a
// directed graph using adjacency
// list representation
class Graph {
	private int V;
 
	// Array of lists for
	// Adjacency List Representation
	private LinkedList<Integer> adj[];
 
	// Constructor
	@SuppressWarnings("unchecked") Graph(int v)
	{
		V = v;
		adj = new LinkedList[v];
		for (int i = 0; i < v; ++i)
			adj[i] = new LinkedList();
	}
 
	// Function to add an edge into the graph
	void addEdge(int v, int w)
	{
		// Add w to v's list.
		adj[v].add(w);
	}
 
	// A function used by DFS
	void DFSUtil(int v, boolean visited[])
	{
		// Mark the current node as visited and print it
		visited[v] = true;
		System.out.print(v + " ");
 
		// Recur for all the vertices adjacent to this
		// vertex
		Iterator<Integer> i = adj[v].listIterator();
		while (i.hasNext()) {
			int n = i.next();
			if (!visited[n])
				DFSUtil(n, visited);
		}
	}
 
	// The function to do DFS traversal.
	// It uses recursive DFSUtil()
	void DFS(int v)
	{
		// Mark all the vertices as
		// not visited(set as
		// false by default in java)
		boolean visited[] = new boolean[V];
 
		// Call the recursive helper
		// function to print DFS
		// traversal
		DFSUtil(v, visited);
	}
 
	// Driver Code
	public static void main(String args[])
	{
		Graph g = new Graph(4);
 
		g.addEdge(0, 1);
		g.addEdge(0, 2);
		g.addEdge(1, 2);
		g.addEdge(2, 0);
		g.addEdge(2, 3);
		g.addEdge(3, 3);
 
		System.out.println(
			"Following is Depth First Traversal "
			+ "(starting from vertex 2)");
 
		// Function call
		g.DFS(2);
	}
}
// This code is contributed by Aakash Hasija