Graph Connectivity from Scratch (2026)
Graph connectivity is a fundamental concept that determines how vertices in a graph are connected to each other. A connected graph has a path between every pair of vertices. Understanding connectivity helps in identifying isolated components, checking if a graph is bipartite, finding bridges and articulation points that are critical to the network structure.
In this tutorial, we will implement algorithms to find connected components, check bipartiteness, identify bridges (edges whose removal disconnects the graph), and find articulation points (vertices whose removal disconnects the graph).
Connected Components
Connected components are maximal subgraphs where every pair of vertices is connected by a path. In an undirected graph, we can find all connected components using BFS or DFS in O(V + E) time. We start from an unvisited vertex, explore all reachable vertices (forming one component), then move to the next unvisited vertex.
For directed graphs, we find Strongly Connected Components (SCCs) using Tarjan's or Kosaraju's algorithm. SCCs are maximal subgraphs where there is a directed path between every pair of vertices within the component.
def connected_components(graph, vertices):
visited = set()
components = []
def bfs(start):
component = []
queue = [start]
visited.add(start)
while queue:
node = queue.pop(0)
component.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
return component
for v in range(vertices):
if v not in visited:
components.append(bfs(v))
return components
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3], 5: []}
print(connected_components(graph, 6)) # [[0,1,2],[3,4],[5]]Bipartite Check
A bipartite graph can be divided into two sets such that every edge connects vertices from different sets. Equivalently, a graph is bipartite if and only if it contains no odd-length cycles. We can check bipartiteness using BFS or DFS by attempting to two-color the graph. Start from any vertex, color it one color, and alternate colors for each level of BFS.
If at any point we find an edge connecting two vertices of the same color, the graph is not bipartite. This algorithm runs in O(V + E) time.
#include
#include
#include
using namespace std;
bool isBipartite(vector>& graph) {
int V = graph.size();
vector color(V, -1);
for (int i = 0; i < V; i++) {
if (color[i] != -1) continue;
queue q; q.push(i); color[i] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
} else if (color[v] == color[u]) return false;
}
}
}
return true;
} Bridges in a Graph
A bridge (or cut edge) is an edge whose removal increases the number of connected components. Bridges are critical edges in a network whose failure would disconnect parts of the network. We can find all bridges using Tarjan's algorithm in O(V + E) time by running DFS and tracking discovery times and low values for each vertex.
The low value of a vertex u is the minimum discovery time reachable from the subtree rooted at u. An edge (u, v) is a bridge if low[v] > disc[u], meaning there is no back edge from v's subtree to u or an ancestor of u.
import java.util.*;
class Bridges {
private int V; private List> adj;
private int timer = 0;
Bridges(int v) {
V = v; adj = new ArrayList<>();
for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
}
List findBridges() {
int[] disc = new int[V], low = new int[V];
boolean[] visited = new boolean[V];
List bridges = new ArrayList<>();
for (int i = 0; i < V; i++)
if (!visited[i]) dfs(i, -1, disc, low, visited, bridges);
return bridges;
}
void dfs(int u, int p, int[] disc, int[] low,
boolean[] vis, List bridges) {
vis[u] = true; disc[u] = low[u] = timer++;
for (int v : adj.get(u)) {
if (!vis[v]) {
dfs(v, u, disc, low, vis, bridges);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) bridges.add(new int[]{u, v});
} else if (v != p) low[u] = Math.min(low[u], disc[v]);
}
}
} Articulation Points
An articulation point (or cut vertex) is a vertex whose removal increases the number of connected components. Finding articulation points is similar to finding bridges but compares low[v] >= disc[u] instead of low[v] > disc[u]. The root of a DFS tree is an articulation point if it has more than one child.
Articulation points represent critical nodes in a network whose failure would isolate parts of the network. The algorithm runs in O(V + E) time using a single DFS traversal.
def articulation_points(graph, vertices):
disc = [0] * vertices
low = [0] * vertices
visited = [False] * vertices
ap = set()
timer = [0]
def dfs(u, parent):
visited[u] = True
disc[u] = low[u] = timer[0]
timer[0] += 1
children = 0
for v in graph[u]:
if not visited[v]:
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
if parent == -1 and children > 1: ap.add(u)
if parent != -1 and low[v] >= disc[u]: ap.add(u)
elif v != parent:
low[u] = min(low[u], disc[v])
for i in range(vertices):
if not visited[i]: dfs(i, -1)
return list(ap)Frequently Asked Questions
What is a connected graph?
A connected graph has a path between every pair of vertices. An undirected graph is connected if it has exactly one connected component. A directed graph is strongly connected if there is a directed path between every pair.
What is a bridge in a graph?
A bridge is an edge whose removal disconnects the graph. It is found using Tarjan's algorithm where low[v] > disc[u] for edge (u, v).
What is a bipartite graph?
A bipartite graph can be divided into two sets where every edge connects vertices from different sets. Equivalently, it has no odd-length cycles. Checkable by two-coloring with BFS/DFS.
How to find articulation points?
Use DFS and track discovery time and low values. A non-root vertex u is an articulation point if it has a child v with low[v] >= disc[u]. The root is an articulation point if it has more than one DFS child.
Originally published on Ayodhyyya. Last updated June 1, 2026.