Data Structures & Algorithms Notes Page

Depth First Search:

What is it:

• Depth First Search goes “deep” cause it visits a vertex, then an adjacent vertex, and then that vertex’s adjacent vertex, and so on

• This way, the distance from the starting vertex increases for each recursive iteration

• In terms of a stack:

  • Whenever node u is visited, recursively visit all of u ’s neighbors
  • As well, DFS wll add all of u ’s unvisited neighbors into the stack
  • Then we will pop the stack and visit that node

Logical Steps:

1. Start at a source node
2. Mark it as visited
3. Recursively visit all of its unvisited neighboring nodes
4. Backtrack when we hit a dead end

Depth First Search with a Stack:

wfs(s)
{
	push s into stack
	while bag isnt empty
		pop v from bag
		for each (v, w) in G dp
			if w is unmarked
				mark w
				push w into bag
}

// Recursively

dfs(v)
{
	if v is unmarked
		mark v
		
		for each(v, w) in G do:
			dfs(w)
}