Graph Connectivity: DFS Applications

Graph Traversal and Depth-First Search (DFS)

Before we dissect graph connectivity, let's briefly revisit graph traversal. Traversing a graph means systematically visiting every vertex and edge. Given your background in Information Technology, you have likely encountered the two primary methods for this: Breadth-First Search (BFS) and Depth-First Search (DFS). For the problems in this lesson, DFS is our tool of choice.

Depth-First Search explores a graph by going as deep as possible down a path before backtracking. Imagine exploring a maze by always taking the first unexplored path you see at a junction. You follow that path to its end, then backtrack to the last junction and try the next unexplored path. This "dive-deep-then-backtrack" strategy is naturally implemented using recursion (which implicitly uses a stack).

The basic algorithm looks like this:

1. Start at a vertex u. Mark it as visited.
2. For each neighbor v of u:
3. If v has not been visited, recursively call DFS on v.

We use a visited array to keep track of vertices we have already seen to avoid infinite loops in graphs with cycles.

Connected Components

In an undirected graph, a connected component is a subgraph in which any two vertices are connected to each other by a path, and which is connected to no other vertices in the supergraph. A graph that is itself connected has exactly one connected component. A graph with several disconnected parts has multiple connected components.

This graph has 10 vertices and 3 connected components. The first component is {0, 1, 2, 3}, the second is {4, 5, 6}, and the third is {7, 8, 9}.

Finding these components is a direct and elegant application of DFS.

Algorithm:

1. Initialize a visited array for all vertices to false and a count of components to 0.
2. Iterate through all vertices of the graph from $v_0$ to $v_{n-1}$.
3. If vertex v_i is not visited, it means we have found a new connected component.
   • Increment count.
   • Start a DFS traversal from v_i. This traversal will visit every vertex in this component.
4. After the loop finishes, count will hold the total number of connected components.

This works because the first DFS call from an unvisited vertex will explore every single node it can reach. Any nodes left unvisited must belong to a different, separate component.

Cut Vertices (Articulation Points)

Now we move to a more subtle concept. A cut vertex, or articulation point, is a vertex in a connected graph whose removal (along with its incident edges) increases the number of connected components. These are critical nodes in a network—single points of failure. For example, a router that connects several sub-networks is an articulation point.

A naive approach would be to remove each vertex one by one and check if the graph becomes disconnected. This is very inefficient, with a time complexity of roughly $O(V(V+E))$. A much more efficient, $O(V+E)$ algorithm exists using a single DFS traversal.

This algorithm relies on two key pieces of information maintained during the DFS traversal:

1. Discovery Time disc[u]: The time (a simple counter) when a vertex u is first visited.
2. Low-link Value low[u]: The lowest discovery time reachable from u (including itself) by traversing zero or more tree edges in the DFS tree and at most one back edge. A back edge is an edge connecting a vertex to one of its ancestors in the DFS tree. Intuitively, low[u] tells us the "highest" ancestor that u or any of its descendants can reach through a shortcut (a back edge).

With these values, we can identify articulation points using two conditions:

1. For the root of the DFS tree: The root is an articulation point if and only if it has two or more children in the DFS tree. If it only has one child, removing the root simply disconnects that one subtree, but doesn't split the graph into more components than before.
2. For any non-root vertex u: Vertex u is an articulation point if it has a child v in the DFS tree such that low[v] >= disc[u].
   • Intuition: This condition low[v] >= disc[u] means that the earliest ancestor reachable from the subtree rooted at v is u itself, or some node below u. There is no back edge from v or its descendants that goes "above" u. Therefore, u is the only connection from the subtree of v to the rest of the graph. Removing u will disconnect v and its descendants.

The following video by Abdul Bari provides one of the clearest explanations of this algorithm available. It walks through the process step-by-step, showing how the disc and low values are computed and used.

Cut Edges (Bridges)

Closely related to cut vertices are cut edges, or bridges. A bridge is an edge in a connected graph whose removal increases the number of connected components. Like articulation points, they represent critical single points of failure, but at the level of connections rather than nodes.

An edge $(u,v)$ in a graph is a bridge if and only if it is not part of any cycle. The algorithm to find bridges is a slight modification of the one for articulation points, also using DFS with discovery times and low-link values.

Let u be a parent of v in the DFS tree. The edge $(u,v)$ is a bridge if there is no back edge from v or any of its descendants to u or any of u's ancestors.

The condition for this is:

Notice the strict inequality! Let's break this down:

• If low[v] < disc[u], it means a descendant of v (or v itself) has a back edge to an ancestor of u. This creates a cycle involving the edge $(u,v)$, so it's not a bridge.
• If low[v] == disc[u], it means a descendant of v (or v itself) has a back edge pointing exactly to u. This also forms a cycle, so $(u,v)$ is not a bridge.
• Only when low[v] > disc[u] are we sure that all paths from v's subtree lead back to v itself, but no higher. This means the edge $(u,v)$ is the sole connection from that component to the rest of the graph.

This video from Jenny's Lectures provides an excellent walkthrough of the bridge-finding algorithm.

Conclusion

In this lesson, we elevated our understanding of graphs from static objects to dynamic structures we can explore. We saw how one fundamental algorithm, Depth-First Search, can be augmented to reveal deep insights about a graph's connectivity.

Key Takeaways:

• Connected Components: A simple loop that repeatedly calls DFS on unvisited vertices is all that's needed to count and identify the connected components of a graph.
• Cut Vertices (Articulation Points): These are critical nodes whose removal disconnects a graph component. They can be found in linear time using a DFS traversal and tracking discovery times and low-link values. A non-root vertex u is a cut vertex if it has a child v such that low[v] >= disc[u].
• Cut Edges (Bridges): These are critical edges whose removal disconnects a graph component. They are identified with a similar DFS-based algorithm. An edge $(u,v)$ (where v is a child of u) is a bridge if low[v] > disc[u].

We have now analyzed the structural integrity of graphs. In our next lesson, we will shift our focus to another classic problem: finding specific kinds of paths within a graph. We will investigate the conditions under which a graph contains an Eulerian path (a path that traverses every edge exactly once) or a Hamiltonian path (a path that visits every vertex exactly once). These problems have famous historical origins and introduce new ways of thinking about graph traversal.