Graphs model relationships between objects. A social network, a road map, the internet, course prerequisites, and even a chessboard are all graphs. If you can describe your data as "things connected to other things," you are looking at a graph problem.

A graph consists of two sets: vertices (also called nodes) and edges (connections between vertices). We write G = (V, E) where V is the set of vertices and E is the set of edges. Each edge connects two vertices. If the edge has a direction (A points to B but not necessarily B to A), the graph is directed. If every edge goes both ways, the graph is undirected.

Degree, Path, and Cycle

The degree of a vertex is the number of edges connected to it. In a directed graph, we distinguish in-degree (edges coming in) and out-degree (edges going out). A vertex with in-degree 0 has no dependencies, which matters for topological sorting.

A path is a sequence of vertices where each consecutive pair is connected by an edge. A cycle is a path that starts and ends at the same vertex. A graph with no cycles is called acyclic. A directed acyclic graph (DAG) appears constantly in interview problems because it models dependency structures like build systems, course prerequisites, and task scheduling.

Connected Components

In an undirected graph, a connected component is a maximal set of vertices where every vertex is reachable from every other vertex. If the graph has one connected component, it is connected. If it has multiple components, they are isolated from each other.

In a directed graph, we talk about strongly connected components (SCCs): maximal subsets where every vertex can reach every other vertex following edge directions. This is more restrictive than undirected connectivity.

Weighted vs Unweighted

Edges can carry weights representing costs, distances, capacities, or any numeric value. An unweighted graph treats all edges as having the same cost. BFS finds shortest paths in unweighted graphs. For weighted graphs, you need Dijkstra's algorithm or Bellman-Ford, which are beyond this lesson.

Why Graphs Matter for Interviews

Many problems that do not mention "graph" are actually graph problems in disguise. A grid where you can move up/down/left/right is a graph where each cell is a vertex and each valid move is an edge. A word transformation problem where you change one letter at a time is a graph where each word is a vertex and edges connect words that differ by one letter. Recognizing the graph structure is often the hardest part of solving the problem.