A graph is a set of objects plus the relationships between them. Whenever your problem is really about connections, a graph is the natural fit. The objects become nodes, and each relationship becomes a link joining two of them.

It models more than you might expect:

• Road maps, where intersections connect by streets
• Social networks, where people connect by friendship
• The web, where pages connect by hyperlinks
• Task schedules, where jobs connect by "must run before"

The payoff is that one toolbox then applies everywhere. Questions like "can I reach here from there" or "what is the cheapest route" become the same search over any of these. You stop writing bespoke logic per domain and reuse proven traversal instead. That reuse is why graphs show up in routing, package managers, and recommendation systems alike.

Vertices are the objects in a graph, and edges are the connections joining pairs of them. People often call vertices nodes and edges links; the words are interchangeable. A single edge always ties exactly two vertices together.

Two more terms describe local structure. The neighbors of a vertex are the vertices directly joined to it by an edge. The degree of a vertex is how many edges touch it, which equals its neighbor count in a simple graph.

Why care? Degree tells you how connected something is. A social account with degree ten million is a hub you must handle carefully. Neighbors are exactly what every traversal reads next, so representing them cheaply drives your whole performance. When someone calls a graph sparse, they mean average degree stays small, and most vertices have few neighbors.

Edges either point one way or go both ways, and that choice is the whole distinction. In an undirected graph an edge means a mutual relationship, like two friends. In a directed graph an edge goes from one vertex to another, like a one-way street or a follow.

The practical effect shows up in reachability. Undirected edges let you travel from either end to the other. Directed edges only let you move along the arrow, so A reaching B never guarantees B reaches A.

Pick based on whether your relationship is symmetric.

• Undirected: friendship, physical roads that run both ways, network cables
• Directed: follows, task ordering, web links, dependencies

Getting this wrong quietly breaks logic. If you model "depends on" as undirected, a topological sort becomes meaningless, and cycle checks stop making sense. Match the edge type to the real relationship first.

A weighted graph attaches a number to every edge, standing for cost, distance, time, or capacity. An unweighted graph treats all edges as equal, so a hop is just a hop. Adding weights changes the question from "how few edges" to "how little total cost".

That shift matters because the cheapest route is often not the shortest by edge count. Three short highway segments can beat one long back road. On a map, weights are miles or minutes; on a network, they might be latency or price.

The consequence for algorithms is real. Plain breadth-first search finds fewest-edge paths, but it ignores weights and gives wrong answers once they exist. You then need weight-aware methods like Dijkstra. So the first thing to ask about any graph problem is whether edges carry meaningful cost, because that single fact decides which algorithm is even correct.

Two layouts dominate, and they trade memory for lookup speed. An adjacency list keeps, for each vertex, a list of its neighbors. An adjacency matrix keeps a grid of size vertices-by-vertices, where cell (i, j) marks whether an edge exists.

The cost difference is the point. A list uses space proportional to O(V + E), which is tiny when edges are few. A matrix always uses O(V^2), even for a nearly empty graph.

list:   A -> [B, C]
matrix: A row = [0, 1, 1, 0]

Speed flips the other way. Checking whether a specific edge exists is O(1) in a matrix but needs scanning a list. Most real graphs are sparse, so adjacency lists are the default choice. You reach for the matrix only when the graph is small or dense, or when you constantly test single edges.

Breadth-first search fans out in layers, visiting everything one step away before anything two steps away. You keep a queue of vertices to process and a visited set so you never revisit. Start by marking the source visited and putting it in the queue.

Then repeat until the queue empties:

• Remove the front vertex
• Look at each of its neighbors
• For any unvisited neighbor, mark it visited and add it to the back

Because the queue is first-in first-out, closer vertices always come out first. That is what produces the ring-by-ring order. Each vertex enters the queue once and each edge is examined once, so the cost is O(V + E).

This layered order is exactly why BFS finds the fewest-edge path in an unweighted graph. The first time you reach a vertex, you reached it by the shortest number of hops.

Depth-first search plunges down one path as far as it can before backing up. You pick a start, mark it visited, then move to an unvisited neighbor and repeat. When a vertex has no unvisited neighbors left, you backtrack to the previous one and try its other branches.

You can drive this with explicit recursion or with a stack.

function dfs(v, seen) {
  seen.add(v);
  for (const n of neighbors(v))
    if (!seen.has(n)) dfs(n, seen); // recurse deeper
}

The visited set stops you from looping forever on cycles. Every vertex and edge is touched once, so DFS also runs in O(V + E) time.

The deep-first order is what makes DFS natural for whole-graph questions: detecting cycles, finding connected components, and producing a topological order. It reaches the far corners of a structure quickly, which suits problems about global shape rather than nearest distance.

Match the traversal to what you actually want to learn. Both visit every reachable vertex in O(V + E) time, so the choice is about order and memory, not raw speed. BFS explores by distance; DFS explores by depth.

Reach for BFS when nearness matters. It finds the fewest-edge path, works well for "closest match" and level-by-level problems, and suits shallow, wide searches. Reach for DFS when structure matters. It fits cycle detection, connected components, and topological sort, where you want to fully explore each branch.

Memory is the other tiebreaker.

• BFS holds a whole frontier, which can be huge on wide graphs
• DFS holds only the current path, but recursion can overflow on very deep graphs

So a rough rule: if you care about shortest hops or the answer is likely nearby, use BFS. If you care about the graph's overall shape, use DFS.

Plain breadth-first search solves this directly, with no fancier algorithm needed. Because BFS reaches vertices in order of hop count, the first time it touches a vertex is along a fewest-edge path. Every edge counts as one step, so fewest edges means shortest.

To recover the actual route, record where you came from. When you first visit a neighbor, store the vertex you arrived from as its parent. Once you reach the target, walk parent pointers backward to rebuild the path, then reverse it.

parent[neighbor] = current; // set on first visit

The whole thing runs in O(V + E) time and space.

The one catch is that this only holds when every edge has the same cost. Add real weights and fewest edges no longer means cheapest, so BFS gives wrong distances. For equal-cost graphs, though, nothing beats it for simplicity.