Depth-First Search (DFS)

A depth-first search algorithm exhausts each one direction before trying another direction.

DFS implementations are based on stacks, either implicitly (recursion) or explicitly (as with queues for BFS).

In DFS, the frontier is managed as a Stack data structure.

• Pros:
  • At best, this algorithm is the fastest. If it “lucks out” and always chooses the right path to the solution (by chance), then depth-first search takes the least possible time to get to a solution.
• Cons:
  • It is possible that the found solution is not optimal.
  • At worst, this algorithm will explore every possible path before finding the solution, thus taking the longest possible time before reaching the solution.

Current struggle → Storing the path of BFS / DFS. I know how to apply it, but returning the exact optimal path it traces is a bit harder.

Implementation using Recursion

DFS can be implemented using recursion. Assumes that the graph is stored as adjacency lists in an array of vectors

vector<int> adj[N];

and also maintains an array

bool visited[N];

that keeps track of visited nodes. Initially, each array value is false, and when the search arrives at node s, the value of visited[s] becomes true. The function can be implemented as follows:

void dfs(int s) {
	if (visited[s]) return;
	visited[s] = true;
	// process node s
	for (auto u: adj[s]) {
		dfs(u);
	}
}

Notice that visited is outside the for loop

This is my intuition. You mark the node as visited while you are inside the DFS function. And then process it. This is NOT the case with BFS, which you mark it inside the for loop. Then, process it a bit later. That is because they use a Queue data structure (NO THATS NOT WHY)

In CS341, they actually put it inside the for loop, so it’s fine in both cases.

It’s just an issue for the first node

v2 (just make sure to set visited to true), more similar to syntax you have in BFS

visited[s] = true;
dfs(s);
 
void dfs(int u) {
	// process node s
	for (auto v: adj[u]) {
      if (!visited[v]) {
    	visited[v] = true;
        dfs(v);
      }
	}
}

Iteratively

Sometimes, you have limited stack space. You can use a Stack instead, keeping the vertices which are currently open in it.

Code Example (old)

# Define the function that removes a node from the frontier and returns it.
def remove(self):
	  # Terminate the search if the frontier is empty, because this means that there is no solution.
	if self.empty():
		raise Exception("empty frontier")
	else:
		  # Save the last item in the list (which is the newest node added)
		node = self.frontier[-1]
		# Save all the items on the list besides the last node (i.e. removing the last node)
		self.frontier = self.frontier[:-1]
		return node

Runtime / Complexity

$V$ are nodes and $E$ are edges.

• Asymptotic running time of DFS is $O(|E|+|V|)$

From CS341