# DFS to find path in an undirected graph

For undirected graphs we just keep track of the previous vertex and find a spanning sub -forest for the graph . We can use this to find paths between vertices by going back to the root vertices of the trees .

DFS(G)
  input: G = (V,E) in adjacency list representation
  output: Vertices labelled by connected components
    connected_component = 0
    for all v in V, set visited(v) = False, previous(v) = Null
    for all v in V
      if not visited(v) then
        connected_component++
        explore(v)
    return previous

Explore(z)
  input: vertex z
    connected_component_number(z) = connected_component
    visited(z) = True
    for all (z, w) in E
      if not visited(w)
        previous(w) = z
        Explore(w)

# Correctness

# Runtime

$O(\vert V \vert + \vert E \vert)$