Depth First Search (DFS)

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: $O(|V|+|E|)$ §

$O(|V|)$ for stack + $O(|E|)$ for checking outgoing edges = $O(|V|+|E|)$

Given a complete graph, DFS would take $O\left(|V|+\frac{1}{2}|(V{|}^2-|V|)\right)$ i.e. $O(n^2)$ Worst-case it has to check the entire graph via it’s edges and store every node in the stack

Applications §

• Cycle detection
• Topological Sorting
• Locating strongly connected components in a graph
• Detecting k-partiteness in graphs

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)