DSA: Graphs, Representation and Traversal

Learn graph terminology, adjacency list and matrix representations, BFS, DFS, cycle detection, topological sort, and bipartite checking.

Graph Terminology

A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices. Graphs model networks, dependencies, maps, and many other real-world relationships.

Core Graph Terms

Understanding these terms is essential before working with any graph algorithm.

  • Vertex (node): a fundamental unit of the graph
  • Edge: a connection between two vertices; can be directed or undirected, weighted or unweighted
  • Degree: number of edges incident to a vertex; in-degree and out-degree for directed graphs
  • Path: a sequence of vertices connected by edges; Cycle: a path that starts and ends at the same vertex
Graph TypeDescription
UndirectedEdges have no direction; edge (u,v) = edge (v,u)
Directed (Digraph)Edges have direction; edge (u,v) goes from u to v only
WeightedEach edge carries a numeric weight/cost
UnweightedAll edges are treated as equal (weight = 1)
DAGDirected Acyclic Graph; no directed cycles used for topological sort
BipartiteVertices split into two sets; every edge connects one set to the other

Graph Representation

The two main representations are the adjacency matrix (2D array) and the adjacency list (array of vectors). The choice affects space usage and the speed of specific operations.

Adjacency Matrix vs Adjacency List

Adjacency list is preferred for sparse graphs. Adjacency matrix is preferred when you need O(1) edge existence checks and the graph is dense.

  • Adjacency matrix: O(V²) space; O(1) edge check; O(V) to list all neighbours
  • Adjacency list: O(V + E) space; O(degree) edge check; O(degree) to list neighbours
  • Most real-world graphs are sparse (E much smaller than V²) so adjacency list wins on space
  • Weighted graphs: store pairs (neighbour, weight) in the adjacency list

Adjacency List and Matrix

C++

Adjacency list stores only existing edges. Matrix gives O(1) existence check at the cost of O(V²) memory.

Breadth-First Search (BFS)

BFS explores all neighbours of the current node before moving deeper. It uses a queue and visits nodes level by level, making it the go-to algorithm for finding shortest paths in unweighted graphs.

BFS Algorithm

Enqueue the start node, mark it visited, then repeatedly dequeue a node, process it, and enqueue all unvisited neighbours.

  • Uses a queue (FIFO) to guarantee level-by-level order
  • visited array prevents revisiting nodes and infinite loops
  • Shortest path in unweighted graph: BFS distance = number of edges from source
  • Time: O(V + E), Space: O(V)

BFS Traversal

C++

Nodes are visited level by level: 0 first, then its neighbours 1 and 2, then their neighbours 3, 4, 5.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. The recursive version uses the call stack implicitly; the iterative version uses an explicit stack.

DFS Algorithm

Mark the current node visited, process it, then recurse on each unvisited neighbour. Backtrack automatically when all neighbours are exhausted.

  • Recursive: mark visited, process, recurse on unvisited neighbours
  • Iterative: push to stack; on each pop, push unvisited neighbours
  • Used for: cycle detection, topological sort, connected components, path finding
  • Time: O(V + E), Space: O(V) for the recursion stack or explicit stack

DFS Traversal (Recursive)

C++

DFS dives deep before backtracking. Node 3 and 4 are reached through 1 before the algorithm backtracks to explore branch 2.

Connected Components

An undirected graph may have multiple disconnected subgraphs called connected components. Run BFS or DFS from every unvisited node; each fresh start discovers one new component.

Counting Components

Iterate over all vertices. Each time you find an unvisited vertex, start a BFS/DFS and increment the component counter.

  • Outer loop over all V vertices; inner BFS/DFS marks the whole component
  • Each vertex is visited exactly once across all BFS/DFS calls: O(V + E) total
  • Useful for: detecting isolated nodes, network connectivity, island counting in grids
  • Union-Find (Disjoint Set Union) is an alternative for dynamic connectivity queries

Count Connected Components

C++

Each unvisited starting node triggers a DFS that colours its entire component. The counter increments once per component.

Cycle Detection in Undirected Graphs

During DFS on an undirected graph, a cycle exists if a visited neighbour is found that is not the parent of the current node. The parent check avoids treating the edge we just came from as a back edge.

DFS Cycle Detection (Undirected)

Track the parent to avoid false positives. A visited non-parent neighbour means a back edge exists, which confirms a cycle.

  • Pass parent node into each DFS call
  • If a visited neighbour is found and it is not the parent, a cycle is detected
  • For disconnected graphs, run the check from every unvisited node
  • Alternatively, Union-Find detects a cycle when both endpoints of an edge are already in the same set

Cycle Detection in Undirected Graph

C++

The parent parameter filters out the reverse of the edge we arrived on, which would otherwise always look like a cycle.

Cycle Detection in Directed Graphs

In a directed graph, a cycle is detected by tracking a recursion stack (recStack). A back edge exists when a neighbour is found that is currently in the active DFS call stack.

DFS with Recursion Stack

visited tracks nodes ever seen; recStack tracks nodes in the current DFS path. A neighbour in recStack means a cycle exists along the current path.

  • recStack[v] = true when v is entered, false when v is fully processed
  • A back edge (edge to a node in recStack) confirms a directed cycle
  • A cross edge (edge to a visited node not in recStack) does not form a cycle
  • Must check all starting nodes for disconnected directed graphs

Cycle Detection in Directed Graph

C++

rec[u] is set to false after u's DFS returns, cleaning it from the active path. Only nodes currently on the stack indicate a cycle.

Topological Sort (DFS)

Topological sort orders vertices of a DAG so that every directed edge u to v has u appearing before v. The DFS approach pushes each fully processed node onto a stack; the stack's top-to-bottom order is the topological order.

DFS Topological Sort

A node is pushed to the result stack only after all nodes reachable from it are fully processed guaranteeing it appears before its dependents.

  • Run DFS; after fully visiting all descendants of a node, push it onto a stack
  • Pop the stack from top to bottom to get the topological order
  • Valid only on DAGs, a cycle makes topological order impossible
  • Multiple valid topological orderings can exist for the same DAG

Topological Sort via DFS

C++

Pushing after all descendants are done ensures prerequisites always appear before the nodes that depend on them.

Topological Sort: Kahn's Algorithm (BFS)

Kahn's algorithm uses in-degrees. Nodes with in-degree 0 have no prerequisites and can be processed first. Processing a node reduces the in-degree of its neighbours; any that reach 0 are enqueued next.

Kahn's BFS Approach

If the number of processed nodes equals V at the end, the graph is a DAG and the processing order is a valid topological sort. If fewer than V nodes are processed, a cycle exists.

  • Compute in-degrees for all nodes
  • Enqueue all nodes with in-degree = 0
  • On dequeue: process node, reduce in-degree of all neighbours, enqueue those that reach 0
  • Cycle detected if processed count < V after queue empties

Kahn's Algorithm (BFS Topological Sort)

C++

In-degree tracks remaining prerequisites. When all prerequisites of a node are resolved, its in-degree hits 0 and it is ready to process.

Bipartite Graph Checking

A graph is bipartite if vertices can be split into two groups such that every edge connects a vertex in one group to a vertex in the other. BFS with 2-coloring detects bipartiteness in O(V + E).

2-Coloring via BFS

Try to colour every vertex with one of two colours such that no two adjacent vertices share the same colour. A conflict means the graph contains an odd-length cycle and is not bipartite.

  • Assign colour 0 to the source, then alternate colours along BFS levels
  • If a neighbour already has the same colour as the current node, the graph is not bipartite
  • Run BFS from every unvisited node to handle disconnected graphs
  • A graph is bipartite if and only if it has no odd-length cycles

Bipartite Check via BFS 2-Coloring

C++

Even cycles can be 2-coloured; odd cycles (like a triangle) cannot. The colour conflict is detected the moment two neighbours share a colour.

Knowledge Check

1. Which graph representation is most space-efficient for a sparse graph?

2. BFS uses which data structure to track nodes to visit next?

3. DFS uses which data structure (explicitly or via recursion)?

4. Topological sort is only valid on which type of graph?

5. Kahn's algorithm detects a cycle in a directed graph when:

6. A graph is bipartite if and only if:

7. In cycle detection for a directed graph using DFS, a back edge is detected when:

8. The time complexity of BFS and DFS on a graph with V vertices and E edges is:

PreviousNext