<aside>
📌 SUMMARY:
DFS takes in an adjacency list which represents an undirected graph, and exploration of the graph is done using the explore subroutine.
If a vertex has not been visited at the start, increment the connected components counter. This counter keeps track of how many independent clusters there are.
We can further use a prev array that when exploring, set a node’s predecessor in it. This allows us to find vertices which are connected.
</aside>
To find components of an undirected graph, we can run DFS which has an explore subroutine that can be recursively used to explore the connected vertices.
This is possible as DFS takes in the graph as an adjacency list.
For a graph that is wholly connected, the component_count stays as 1.

depth_first_search(G):
# input: G=(V,E) in adjacency list representation
# output: vertices labelledby connected components
component_count = 0 # counter for current connected component number
# array to keep track if we visited a vertex yet, initialize all to False at the beginning
for all v in V:
visited(v) = False
for all v in V:
if not visited(v):
# number of connected components; ie number of separated graphs. If only 1 undirected graph that is fully connected, then this remains as 1
connected_component++
explore(v)
explore Subroutineexplore(z)
# first time visiting z, so store its connected component number as the current count for the connected components
# this is being stored per vertex
connected_component_number = component_count
# set z as visited
visited(z) = True
# now we explore all edges out of z, possible as G given as adjacency list, so we can just look through the linked list for z's neighbors
for all (z,w) in E:
if not visited(w): # if w is not visited yet, we recursively explore from w
explore(w)
By maintaining a prev array, we can keep track of how the vertices are connected, where when we first visit a vertex from a predecessor, we link those 2 in the prev array.
prevdepth_first_search(G):
# input: G=(V,E) in adjacency list representation
# output: vertices labelledby connected components
connected_component = 0
for all v in V:
visited(v) = False
# to keep track of predecessor vertex
# initialize the prev array to null for every vertex
prev(v) = None
for all v in V:
if not visited(v):
connected_component++
explore(v)
explore subroutineexplore(z)
connected_component_number = connected_component
visited(z) = True
for all (z,w) in E:
if not visited(w):
explore(w)
# first time visiting a vertex w, so we can set the previous of w to its predecessor vertex z
prev(w) = z
<aside> 📌 SUMMARY: To perform DFS on Directed Graphs, we introduce a clock which is then used for the pre- and post-order numbering of visited vertices. When we first visit a vertex, store the current clock value as its pre-order number and when popping back up, store the current clock value as its post-order number. Increment the clock value in both cases 4 types of edges can exist in a Directed Graph: tree edge, back edge, forward edge and cross edge. Only for back edges, the $\text{post}(z) < \text{post}(w)$ If back edges exist, that means the graph has a cycle and vice-versa
</aside>
To get connectivity information on directed graphs, we use a clock which increments whenever we store the clock’s value as the pre- and post- value in a vertex during the subroutine exploration.
Pre-order is clock value when first visiting the vertex
Post-order is clock value when finished exploring the vertex
depth_first_search(G):
# initialize the clock
clock = 1
for all v in V:
visited(v) = False
prev(v) = None
for all v in V:
if not visited(v):
connected_component++ # optional
explore(v)
explore subroutine with clockexplore(z)
# store z's pre-order number as the current clock value when first visiting z
# then increment the clock value
pre(z) = clock
clock++
visited(z) = True
for all (z,w) in E:
if not visited(w):
explore(w)
# after exploring vertex z, set z's post-order number to be the current clock value
# then increment the clock value
post(z) = clock
clock++
For each vertex at discovery time, we store the current clock’s value as the pre-order number for that vertex then increment the clock.
When discovery is done this way, we can mark with a black arrow to show this. Travel all the way until we reach the end of the discovery (vertex cannot be recursed further) then start popping backward.
When popping back (finish time), use the current clock’s value as the post-order number.
As we start traversing backwards, if we see a vertex has other connections:
