Depth First Search

Travels the graph by going as deep as it can. It does this by visiting all the child vertices before proceeding to the next vertex.

Algorithm

$O(V+E)$

1. Initialization:
   • Set all vertices as unvisited.
   • For every unvisited vertex call a recursive function.
2. Recursion:
   • Set the vertex as visited and add it to the result.
   • For every neighbor of the current vertex:
     • If it hasn't been visited, call the recursive function on it.
3. Termination: Repeat step 2 until all vertices have been visited

C++ code

vector<T> Graph<T>::dfs() const {
	// Set all vertices as unvisited
	for (Vertex<T> *i: getVertexSet()) {
		i->setVisited(false);
	}
	vector<T> res;
	// Call the auxiliary function until all vertices are visited
	for (Vertex<T> *i: getVertexSet()) {
		if (!i->isVisited()) {
			dfsVisit(i, res);
		}
	}
	return res;
}

void Graph<T>::dfsVisit(Vertex<T> *v, vector<T> &res) const {
	// Set the vertex as visited, then recursively call the function
	v->setVisited(true);
	res.push_back(v->getInfo());
	for (Edge<T> edge: v->getAdj()) {
		if (!edge.getDest()->isVisited()) {
			dfsVisit(edge.getDest(), res);
		}
	}
}