GraphsData structureaka simple graph, symmetric graph

Undirected Graph

Vertices joined by two-way edges: {u, v} can be traversed in either direction.

▶ Visualize Pattern: Breadth-First Search Practice (7)

Progress

Definition

An undirected graph G = (V, E) has edges that are unordered pairs {u, v}. Each edge is stored twice in an Adjacency List (v in adj[u] and u in adj[v]) or as a symmetric Adjacency Matrix. The degree of a vertex is its number of incident edges, and Σ deg(v) = 2|E| (the handshake lemma).

Because reachability is symmetric, "connected" has one meaning and the vertices partition cleanly into Connected Components. This makes Union-Find (Disjoint Set Union) the natural tool for incremental connectivity, and it gives minimum spanning trees (Kruskal's Algorithm, Prim's Algorithm) their meaning.

Cycle detection is simpler than in a digraph: during DFS, any visited neighbor other than the parent closes a cycle. Undirected graphs also support the Bipartite Check, Bridges, and Articulation Points in a single DFS.

symmetric edgesconnected componentsdegreebipartitespanning tree

Intuition

A mental model before the formal terms.

A road map with only two-way streets. If you can drive from A to B you can drive back. Towns reachable from each other form an island; the number of islands is the number of connected components.

Friendship is the other classic picture: if Alice is friends with Bob, Bob is friends with Alice. "How many friend groups?" is a components question; "can we split everyone into two teams with no friends on the same team?" is a bipartite question.

How it works

addEdge(u, v): adj[u].push(v) and adj[v].push(u). In a matrix, set both M[u][v] and M[v][u].
Traverse with Breadth-First Search (BFS) or Depth-First Search (DFS) from an unvisited vertex; every vertex reached belongs to the same component. Repeat from the next unvisited vertex to count components.
Cycle detection by DFS: keep visited[] and pass the parent; an edge to a visited vertex that is not the parent is a back edge → cycle. Alternatively, Union-Find (Disjoint Set Union): an edge whose endpoints are already in the same set closes a cycle.
Two-colour the graph with BFS to test bipartiteness; a conflict (neighbor with the same colour) means an odd cycle.
A connected undirected graph on V vertices with exactly V - 1 edges is a tree; with more edges it contains a cycle.

Why it works

Symmetry makes reachability an equivalence relation, so components are well-defined and DFS/BFS from any vertex discovers the whole component.

In an undirected DFS there are only tree edges and back edges — no cross or forward edges — because when an edge {u, v} is examined from u, v is either undiscovered (tree edge) or an ancestor still on the stack (back edge). That is why the parent check suffices for cycle detection.

Operations

Operation	Description	Cost
addEdge(u, v)	Append to both adjacency lists.	O(1)
removeEdge(u, v)	Delete from both lists.	O(deg(u) + deg(v))
neighbors(u)	Iterate adj[u].	O(deg(u))
degree(u)	Length of adj[u].	O(1)
hasEdge(u, v)	Scan the shorter of the two lists.	O(min(deg(u), deg(v)))
components()	Repeated BFS/DFS or union-find over all edges.	O(V + E)
hasCycle()	DFS with parent tracking, or union-find.	O(V + E)

Recognition

How to tell a problem wants this.

Symmetric words: "connected to", "friends with", "adjacent", "road between", "wire between".
The input is a list of unordered pairs and there is no notion of direction.
Questions about number of components, islands, groups, provinces, or whether a redundant connection exists.
Grid problems where you can move in 4 or 8 directions are implicit undirected graphs.

“minimum steps” → Breadth-First Search “connected groups” → Depth-First Search “connected groups” → Union-Find

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Breadth-First Search (BFS) visualization.

Graph — One edge per line: "A B". Optional "source: A" / "target: F" lines.

Queue (front → back)

1/42Start BFS from A. Put it in the queue and mark it visited with distance 0.

Current nodeIn queueVisitedBFS tree edge

PseudocodeLearn Breadth-First Search (BFS) →

1queue = [source]; visited = {source}
2while queue not empty:
3  u = queue.popleft()
4  for v in neighbors(u):
5    if v not in visited:
6      visited.add(v); parent[v] = u
7      queue.append(v)

Complexity

best O(V + E)

avg O(V + E)

worst O(V + E)

space O(V)

Speed

Pseudocode

1add_edge(u, v): adj[u].append(v); adj[v].append(u)
2count_components(): seen = {}; c = 0
3  for u in V: if u not in seen: c += 1; dfs(u)
4has_cycle(): dfs(u, parent):
5  seen.add(u)
6  for v in adj[u]: if v == parent: continue
7    if v in seen or dfs(v, u): return True
8  return False

Implementation

1class UndirectedGraph:
2    """An undirected graph: every edge is stored as two half-edges, so the
3    adjacency relation is symmetric and degree counts both directions."""
4 
51 · State: adj[u] lists every neighbour; each edge appears in two rows
6    def __init__(self, n: int) -> None:
7        self.adj: list[list[int]] = [[] for _ in range(n)]
8        self.edge_total = 0
9 
102 · One logical edge, two stored half-edges (self-loops stored once)
11    def add_edge(self, u: int, v: int) -> None:
12        self.adj[u].append(v)
13        if u != v:
14            self.adj[v].append(u)
15        self.edge_total += 1
16 
17    def __len__(self) -> int:
18        return len(self.adj)
19 
20    def neighbours(self, u: int) -> list[int]:
21        return self.adj[u]
22 
23    def degree(self, u: int) -> int:
24        return len(self.adj[u])
25 
263 · Handshake lemma: the degrees sum to exactly 2E
27    def degree_sum(self) -> int:
28        return sum(len(row) for row in self.adj)  # == 2 * edge_total
29 
304 · Connected components: reachability is symmetric, so DFS partitions
31    def components(self) -> list[int]:
32        comp = [-1] * len(self.adj)
33        c = 0
34        for s in range(len(self.adj)):
35            if comp[s] != -1:
36                continue
37            stack = [s]
38            comp[s] = c
39            while stack:
40                u = stack.pop()
41                for v in self.adj[u]:
42                    if comp[v] == -1:
43                        comp[v] = c
44                        stack.append(v)
45            c += 1
46        return comp
47 
485 · A tree is a connected graph with exactly V-1 edges and no cycle
49    def is_tree(self) -> bool:
50        if self.edge_total != len(self.adj) - 1:
51            return False
52        return all(c == 0 for c in self.components())

Walkthrough

[[] for _ in range(n)] builds distinct rows, avoiding the [[]] * n aliasing trap.
if u != v keeps a self-loop stored once, so degree and edge_total stay consistent with each other.
sum(len(row) for row in self.adj) is the handshake lemma; the generator avoids materialising an intermediate list.
while stack: is the Pythonic empty test, and stack.pop() from the end is O(1).
all(c == 0 for c in self.components()) short-circuits on the first non-zero label.

Complexity (this implementation)

time O(1) add_edge, O(V + E) components and is_tree · space O(V + E) storage, O(V) for the component labels

Language notes

all() and any() over generators short-circuit, so the connectivity check stops at the first vertex in a second component.
networkx.connected_components(G) and networkx.is_tree(G) cover both of these for real work, with labelled vertices.
[-1] * n is safe because int is immutable; [[]] * n is the version that aliases.
For a union-find alternative, scipy.sparse.csgraph.connected_components operates directly on a sparse adjacency matrix.

Common mistakes in this language

Building self.adj with [[]] * n and having every vertex share one neighbour list.
Using stack.pop(0) to get BFS-like order, which is O(n) per call — use collections.deque.popleft instead.
Deriving edge_total from degree_sum() // 2 in a graph with self-loops.

Language differences that matter here

The symmetric double-store is identical everywhere; what differs is the empty-container idiom that builds it — std::vector<std::vector<int>>(n) is safe, while fill([]) in JS/TS and [[]] * n in Python both alias.
Short-circuiting "all elements satisfy": C++ std::all_of, JS/TS Array.prototype.every, Python all() over a generator — same semantics, three spellings.
Library answers exist for connected components in Python (networkx, scipy.sparse.csgraph) and C++ (Boost.Graph), but not in the JS/TS standard library.
Reduce/accumulate seeds: JS/TS reduce throws on an empty array without an initial value, Python sum() returns 0, and C++ std::accumulate requires the init argument by signature.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Vertex by id.
Search	O(deg(u))	O(V)	Edge (u, v) lookup by scanning u's list.
Insert	O(1)	O(1)	Append an edge.
Delete	O(deg(u))	O(V)	Remove an edge from u's list.
Update	O(deg(u))	O(V)	Find the edge, then change its weight.
Components	O(V + E)	O(V + E)
Cycle check	O(V + E)	O(V + E)
Bipartite check	O(V + E)	O(V + E)
Space	O(V + E)		Adjacency list stores each edge twice.

Advantages & disadvantages

Advantages

Simplest graph model; most textbook algorithms (MST, components, bipartite, bridges) are defined on it.
Union-Find (Disjoint Set Union) gives near-O(1) incremental connectivity.
Cycle detection needs only the parent check, not three colours.

Disadvantages

Each edge is stored twice in an adjacency list (2E entries).
Cannot express asymmetric relations; ordering problems are meaningless.
Edge deletion is O(deg) per endpoint unless adjacency sets are used.

Use cases

Social networks, friend groups, communities.
Road, rail, and utility networks; minimum spanning trees for cabling.
Grid flood-fill: number of islands, rotting oranges, surrounded regions.
Redundant Connection: find the edge that creates a cycle with Union-Find (Disjoint Set Union).
Bipartite matching and two-colouring problems.

Use it when

The relation is symmetric.
You need components, spanning trees, bipartiteness, bridges, or articulation points.
Incremental connectivity queries — pair with Union-Find (Disjoint Set Union).

Avoid it when

The relation has direction (prerequisites, links) — use a Directed Graph.
The structure is a tree with a designated root — parent pointers or child lists are lighter.
You need constant-time edge existence on a dense graph — use an Adjacency Matrix.

Alternatives

Directed Graph Adjacency Matrix Edge List Union-Find (Disjoint Set Union)

Common mistakes

Adding the edge in only one direction, so BFS misses half the graph.
Cycle detection without the parent check — every tree edge looks like a cycle because the parent is already visited.
Parent check by vertex fails with parallel edges (multigraph); track the edge id instead.
Counting each edge twice when summing degrees or edges.
Assuming the graph is connected and running one BFS from vertex 0.

Interview patterns

Number of Islands / Number of Connected Components: flood-fill or union-find.
Redundant Connection: the first edge that joins two vertices already connected.
Is Graph Bipartite: BFS two-colouring.
Critical Connections: bridges via Tarjan low-link.
Clone Graph: BFS with a hash map from original to copy.
Minimum spanning tree: Kruskal on sorted edges or Prim with a heap.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner
Recursion versus iterationIntermediate
When space complexity mattersIntermediate

Mock interviews

Course ScheduleIntermediate
Network Delay TimeAdvanced
Number of IslandsIntermediate

Interview problems

Number of Islandsmedium Clone Graphmedium Number of Connected Componentsmedium Is Graph Bipartite?medium Critical Connections in a Networkhard Min Cost to Connect All Pointsmedium Redundant Connectionmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related