← Back to the graphs page
Undirected Graph
Edges have no direction — if A connects to B, B connects to A. The simplest mental model: friendships, roads, network cables.
What to know
- Stored as adjacency list (sparse, most common) or adjacency matrix (dense, O(1) edge check).
- A connected component is a set of nodes all reachable from each other.
- Cycles exist whenever edges ≥ nodes within a component.
- Degree of a node = number of edges touching it.
In the wild: Facebook friend graphs, LAN topology, road networks without one-way streets.
Algorithms to reach for
BFS (Breadth-First Search)
O(V + E)Shortest path in unweighted graphs, level-order exploration
DFS (Depth-First Search)
O(V + E)Explore all paths, detect cycles, flood fill
Union-Find (Disjoint Set)
O(α(n)) per opCount/merge connected components, detect cycles online
Tarjan’s bridges & articulation points
O(V + E)Find edges/nodes whose removal disconnects the graph
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.