Graph Depth-First Search (DFS)

Related data structure**:

• ADT - Graph

AlgorithmData_StructureGraphDFS

---

Graph Depth-First Search is a traversal method that prioritise going as far as possible and then backtracks when no further paths are available.

Implementation

The “go as far as possible and return” algorithm paradigm is usually implemented based on recursion. Similar to Graph Breadth-First Search (BFS), in DFS, we also use a hash set visited to record all visited vertices to avoid revisiting.

List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
	List<Vertex> res = new ArrayList<>();
	Set<Vertex> visited = new HashSet<>();
	def(graph, visited, res, startVet);
	return res;
}
 
void dfs(GrapghAdjList graph, Set<Vertex> visited, List<vertex> res, Vertex vet) {
	res.add(vet);
	visited.add(vet);
	for (Vertex adjVet : graph.adjList.get(vet)) {
		if (visited.contains(adjVet))
			continue;
		// recursive call
		dfs(graph, visited, res, adjVet);
	}
}

Time complexity

All vertices will be visited once, using $O(|V|)$ time, all edges will be visited twice for undirected graph using $O(2|E|)$; with overall time complexity $O(|V|+|E|)$.

---

Back to parent node: ADT - Graph

Reference:

• https://www.hello-algo.com/en/chapter_graph/graph_traversal/