A search algorithm that fully traverses a possible path before checking it’s neighbours. It dives in ‘depth first’. It uses a the stack ADT to store nodes.

Pseudocode

Algorithm DFS(Graph, start,end):

	stack ← Stack ADT
	output ← List
	visited ← Set ADT
	cwn ← Node ADT

	Push start to stack
	
	While stack is not Empty do: #O(|V|)
		cwn ← Popped value from stack
		If cwn not in visited then:
			Add cwn to visited
			Add cwn to output
			For edge cwn-v in outgoing edges do: #O(|E|)
				If v = end then:
					Add end to output
					Return output
				Else if v not in seen_nodes then:
					Push v to stack
				End if
			End do
		End if
	End do
	Return "FAIL"
End Algorithm

Complexity

Time Complexity:

for stack + for checking outgoing edges =

Given a complete graph, DFS would take i.e. Worst-case it has to check the entire graph via it’s edges and store every node in the stack

Applications

Implementation

Iterative
import networkx as nx
from ADTs import Stack
 
def DFS(G: nx.Graph, start_node=None, end_node=None):
    # Setting start_node to the 'first' node in a graph
    if start_node == None:
        start_node = list(G)[0]
 
    # Initialize the Stact ADT to keep track of nodes
    # And a set of 'seen' nodes
    S = Stack()
    seen_nodes = set()
    output = []
    
    S.push(start_node)    
 
    while S.isFull():
        cwn = S.pop()    # Set Current Working Node to popped value
        # Do end_node check early
        # Note the check if a node is seen is done AFTER removing it from stack
        if cwn not in seen_nodes:
            seen_nodes.add(cwn)
            output.append(cwn)
            if cwn == end_node and end_node != None:
                return (output)
            neighbours = list(G.adj[cwn])
            neighbours.reverse()
            for neighbour in neighbours:
                S.push(neighbour)
    return output
Recursive
import networkx as nx
 
def Recursive_DFS(G: nx.Graph, start, end=None, output=list(), seen_nodes=set()):
    seen_nodes.add(start)
    output.append(start)
    if start == end and end != None:
        return (output)
    neighbours = list(G.adj[start])
    for neighbour in neighbours:
        if neighbour not in seen_nodes:
            Recursive_DFS(G, neighbour)
    return (output)