Graphs.

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

Real-world examples include:

• 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 the same algorithms work on all of these. Questions like "can this node reach that one" or "what is the cheapest route" become the same search over any of them. That reuse is why graphs show up in routing, package managers and recommendation systems.

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

The neighbors of a vertex are the vertices directly joined to it by an edge. Its degree is how many edges touch it, which equals its neighbor count in a simple graph. In a directed graph, degree splits into in-degree and out-degree.

Degree tells you how connected something is. A social account with degree ten million is a hub you must handle carefully. Neighbors are what every traversal reads next, so storing them cheaply drives your whole performance. Calling a graph sparse means its 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 path from A to B never guarantees a path back.

Pick based on whether the relationship is symmetric.

• Undirected for friendship, two-way roads and network cables
• Directed for follows, web links, and dependencies like task ordering

Getting this wrong breaks logic without an error. 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 or time. Some graphs use it for capacity instead. An unweighted graph treats all edges as equal, so every edge counts as one step. Weights change the question from "how few edges" to "how little total cost".

That matters because the cheapest route is often not the shortest by edge count. Three short highway segments can beat one long back road. Weights are miles or minutes on a map, and latency or price on a network.

Breadth-first search finds fewest-edge paths, but it ignores weights and gives wrong answers once they exist. You then need a weight-aware method like Dijkstra. So first ask whether edges carry a real cost, because that decides which algorithm is correct.

An adjacency list keeps, for each vertex, a list of its neighbors. An adjacency matrix keeps a grid with one row and one column per vertex. The cell at row i, column j marks whether an edge joins those two vertices.

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

These two layouts dominate, and they trade memory for lookup speed. 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.

Lookup speed favors the matrix. Checking whether a specific edge exists is O(1) in a matrix but needs a scan of the list.

Most real graphs are sparse, so adjacency lists are the default choice. Use the matrix only when the graph is small or dense, or when you test single edges constantly.

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 follows 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 recursion, which uses the call stack, or with an explicit 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. DFS visits each vertex once and scans each edge once, so it runs in O(V + E) time, the same as BFS.

That depth-first order makes DFS natural for whole-graph questions, such as detecting cycles, finding connected components and producing a topological order. It suits problems about the graph's overall structure rather than the nearest distance.

Use BFS when nearness matters and DFS when the graph's structure matters. 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, and DFS explores by depth.

BFS finds the fewest-edge path, works well for "closest match" and level-by-level problems, and suits shallow, wide searches. DFS 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 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.