= Solution
<Depth-first search> marks a vertex when first reached, then recursively explores each still-unvisited neighbour before returning. To cover the whole graph, restart from every vertex not reached by earlier searches:
``
visit(v):
visited[v] = true
for w in adjacency[v]:
if not visited[w]:
visit(w)
for v in V:
if not visited[v]:
visit(v)
``
For a <directed graph>, use outgoing neighbours; for an <undirected graph>, use both incidences of each edge. Each vertex is discovered once and each stored incidence is inspected once. Thus with <adjacency lists> the <running time> is \b[$O(|V|+|E|)$] and the visited information and recursion stack use $O(|V|)$ space. An <adjacency matrix> representation instead requires scanning $|V|$ possible neighbours per visited vertex, giving $O(|V|^2)$ time.
Back to article page
