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
- Cycle detection
- Topological Sorting
- Locating strongly connected components in a graph
- Detecting k-partiteness in Graph
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)