Depth First Search

How does it work?

• Recursively go through graph, backtracking as necessary

DFS-visit (Vertices, adjacency list, specific vertice s):
for v in Adjacency list:
 if v not in parent:
  parent[v] = s
  DFS-visit(V,Adj,s)

DFS:
for s in V:
  if s not in parent:
    parent[s] = none
    DFS-visit(v,adj,s)