Graph Representation, BFS, DFS and Connectivity

A graph models entities and arbitrary relationships among them. Formally, a graph G = (V, E) contains a set of vertices V and a set of edges E. Vertices can represent cities, users, tasks, web pages or program states. Edges can represent roads, friendships, dependencies, links or valid transitions.

Graphs are more general than trees. They may contain cycles, several routes between vertices and disconnected regions. Algorithms must therefore record which vertices have already been discovered; blindly following edges can revisit a cycle forever.

Directed, Undirected and Weighted Graphs

An undirected edge {u, v} connects its endpoints symmetrically. A directed edge (u, v) has orientation from u to v; its existence does not imply (v, u). A weighted graph associates a cost, distance, capacity or another value with each edge. An unweighted graph can be viewed as assigning equal unit cost to every edge.

The degree of an undirected vertex is the number of incident edge ends. In a directed graph, indegree counts incoming edges and outdegree counts outgoing edges. A self-loop contributes according to the representation and degree convention; in an undirected degree count it contributes two incident ends.

A walk may repeat vertices and edges. A trail does not repeat an edge. A simple path does not repeat a vertex. A cycle begins and ends at the same vertex without repeating other vertices. Two vertices are connected in an undirected graph if a path joins them. A maximal group of mutually connected vertices is a connected component.

Directed connectivity has several meanings. Vertex v is reachable from u if a directed path goes from u to v. A directed graph is strongly connected when every vertex can reach every other; its maximal strongly connected regions are strongly connected components. Weak connectivity ignores edge direction.

Adjacency Matrices

For V indexed vertices, an adjacency matrix is a V × V array. In an unweighted graph, matrix[u][v] records whether edge (u, v) exists. In a weighted graph it may store the weight, while a distinguished value represents no edge.

Edge existence is tested in O(1) time. Adding or removing a known edge is also constant-time. Storage is Theta(V²) whether the graph has few or many edges. Enumerating all neighbors of one vertex scans an entire row in Theta(V) time.

An undirected graph’s matrix is symmetric when parallel edges are not separately represented. Directed matrices need not be symmetric. A matrix suits dense graphs and algorithms that repeatedly need constant-time adjacency checks. Care is needed when zero is a valid edge weight; zero cannot simultaneously mean “no edge” without a separate presence indicator.

Adjacency Lists

An adjacency-list representation associates each vertex with a collection of outgoing neighbors. A directed edge (u, v) appears in u’s list. An undirected edge usually appears twice, once in each endpoint’s list. Weighted entries store both the neighbor and edge weight.

Storage is O(V + E) for a directed graph and still O(V + E) asymptotically when undirected edges are stored twice. Enumerating neighbors of u takes time proportional to its degree. Testing a particular edge may require scanning that list, although a hash-set neighbor container can provide expected constant-time membership at additional cost.

Adjacency lists suit sparse graphs, where E is far below V² and are the standard representation for traversal. The exact order of neighbors affects the order produced by BFS or DFS but usually not the set of reached vertices.

An edge list simply stores all edges. It is compact and useful for algorithms such as Kruskal’s, which process edges globally, but it is inefficient for repeatedly finding a vertex’s neighbors.

Breadth-First Search

Breadth-first search or BFS, explores vertices in layers of increasing edge distance from a start vertex. It uses a FIFO queue. The start is marked discovered and enqueued. Repeatedly, the algorithm dequeues a vertex, examines each outgoing neighbor and marks and enqueues every neighbor not previously discovered.

A vertex should normally be marked when it is enqueued, not when later dequeued. Early marking ensures that the first discovering edge claims it and prevents several neighbors from placing duplicate copies into the queue.

The BFS invariant is that queued vertices have been discovered but not fully processed and their distances are nondecreasing from front to rear. When a vertex u at distance d first discovers v, set distance[v] = d + 1 and parent[v] = u. Because all paths with fewer edges have already been considered, this first distance is minimum in an unweighted graph.

Following parent links backward from a reachable destination reconstructs one minimum-edge path to the source. Reverse the collected sequence to obtain source-to-destination order. If the destination was never discovered, no such path exists from that source.

With adjacency lists, every vertex is enqueued at most once and every stored edge is examined once, so time is O(V + E) and auxiliary storage is O(V). With an adjacency matrix, scanning a full row for every reached vertex makes full traversal O(V²).

Depth-First Search

Depth-first search or DFS, follows one path as far as possible before returning to the most recent vertex with an unexplored edge. Recursive DFS uses the runtime call stack. Iterative DFS uses an explicit stack.

On entering a vertex, mark it discovered. For each outgoing neighbor, recursively visit it if unvisited. Processing after all children have returned gives a completion or finish order. Recursive depth can reach O(V) on a long path, so an explicit stack avoids dependence on call-stack capacity.

An iterative DFS must define when discovery occurs and how neighbors are pushed. Marking on push prevents duplicates. If the goal is to reproduce a recursive left-to-right order, push neighbors in reverse of the desired visit order because the stack removes the last pushed neighbor first.

With adjacency lists, DFS takes O(V + E) time and O(V) auxiliary state. DFS does not generally find minimum-edge paths because it may follow a long branch before considering a shorter alternative.

Traversing Disconnected Graphs

One BFS or DFS reaches only vertices reachable from its start. To traverse an entire graph, iterate through all vertices and launch a traversal whenever an unvisited vertex is found. In an undirected graph, each launch discovers one connected component, so the number of launches is the component count.

The parent links produced by a traversal form a tree for each component, collectively called a traversal forest. These edges are not necessarily all graph edges. Non-tree edges reveal additional relationships and may establish cycles.

Cycle Detection

In an undirected DFS, encountering a previously visited neighbor indicates a cycle only when that neighbor is not the current vertex’s parent. The edge back to the parent appears because each undirected edge is represented from both endpoints and is part of the traversal tree itself.

Directed cycle detection uses three states: unvisited, active and finished. A vertex is active while it lies on the current DFS path. An edge from the current vertex to an active vertex is a back edge and proves a directed cycle. An edge to a finished vertex does not by itself prove one.

For undirected graphs, a disjoint-set structure can also detect cycles while edges are added: if both endpoints already belong to the same set, adding their edge closes a cycle.

Topological Ordering

A topological ordering of a directed graph places every source of an edge before its destination. Such an ordering exists exactly for directed acyclic graphs or DAGs. It models prerequisite constraints such as course dependencies and build steps.

DFS can produce an ordering by placing each vertex into output after all its outgoing descendants finish, then reversing finish order. Active-state cycle detection must reject cyclic input. Kahn’s algorithm instead counts indegrees, queues every zero-indegree vertex, repeatedly removes one and reduces the indegrees of its outgoing neighbors. If fewer than V vertices are produced, a directed cycle prevents a complete ordering.

Topological order need not be unique. When several vertices currently have no unmet predecessor, choosing a different one creates another valid result.

Bipartite Graphs

An undirected graph is bipartite if its vertices can be divided into two sets such that every edge crosses between the sets. BFS or DFS can assign alternating colors. Give an uncolored start one color and assign every newly discovered neighbor the opposite color. An edge whose endpoints receive the same color proves the graph is not bipartite.

Each disconnected component needs its own starting color. A graph is bipartite exactly when it contains no odd-length cycle. Applications include matching applicants to positions and separating two kinds of interacting entities.

Choosing and Testing a Representation

Representation changes the cost of an algorithm even when its logical steps are unchanged. An adjacency matrix offers direct edge tests and predictable dense storage. An adjacency list makes traversal proportional to actual graph size. An edge list supports algorithms that sort or scan all edges.

Graph code should test isolated vertices, self-loops, parallel edges if allowed, disconnected components, a single vertex, directed one-way reachability and cycles. Vertex identifiers should be validated before indexing. For undirected adjacency lists, insertion and deletion must update both directions consistently.

BFS and DFS are foundations for richer algorithms. BFS exposes unweighted distance layers. DFS exposes nested reachability and completion structure. Their correctness depends on explicit discovery state and their efficiency depends on selecting a graph representation that matches the operations performed.