Graphs — Complete DSA Graph Theory

Theory

What is a Graph?

A Graph is a non-linear data structure consisting of a finite set of vertices (nodes) connected by edges. Unlike trees, graphs have no hierarchical structure — any node can connect to any other.

Formally, a graph G = (V, E) where V is the set of vertices and E is the set of edges. Graphs model relationships between objects, making them one of the most versatile data structures in computer science.

Memory representation

// Graph G = (V, E)
V = {0, 1, 2, 3, 4} // vertices
E = {(0,1), (1,2), (2,3)} // edges

// Adjacency List (most common)
vector<vector<int>> adj(V);
adj[u].push_back(v); // add edge u → v

Why Graphs? Because real-world relationships are rarely linear or hierarchical. Social networks, road maps, dependency systems, and the entire web are all graphs. A graph can represent any pairwise relationship between entities.

Terminology

Vertex (Node)

A fundamental unit of a graph. Represents an entity or data point. Denoted as V in G = (V, E).

Edge

A connection between two vertices. Can be directed (one-way) or undirected (two-way). Denoted as E in G = (V, E).

Directed Graph

Edges have direction — an edge from u to v does not imply an edge from v to u. Represented with arrows.

Undirected Graph

Edges have no direction — if (u,v) exists, then (v,u) also exists implicitly. Represented with lines.

Weighted Graph

Each edge has an associated weight or cost. Used for shortest path, minimum spanning tree, and network flow problems.

Unweighted Graph

All edges are treated equally (weight = 1). BFS naturally finds shortest paths in unweighted graphs.

Connected Graph

There is a path between every pair of vertices. A disconnected graph has at least two components with no path between them.

Disconnected Graph

At least one pair of vertices has no path connecting them. The graph consists of multiple connected components.

Cyclic Graph

Contains at least one cycle — a path that starts and ends at the same vertex with no repeated edges.

Acyclic Graph

Contains no cycles. A Directed Acyclic Graph (DAG) is essential for topological sorting and scheduling.

Degree

Number of edges incident to a vertex. In directed graphs: Indegree (incoming) and Outdegree (outgoing).

Path

A sequence of vertices where each consecutive pair is connected by an edge. A simple path has no repeated vertices.

Cycle

A path that starts and ends at the same vertex. Simple cycle has no repeated vertices except start/end.

Tree as a Graph

A tree is a connected acyclic undirected graph with exactly V-1 edges. Every tree is a graph, but not vice versa.

Graph Density

Ratio of actual edges to maximum possible edges. Sparse: E ~ O(V). Dense: E ~ O(V^2).

Real-world examples

Social Networks

Users are vertices; friendships/follows are edges. Facebook (undirected), Twitter/X (directed), LinkedIn (weighted by connection strength).

Google Maps

Intersections are vertices; roads are weighted edges (distance/time). Shortest path algorithms find optimal routes.

Computer Networks

Routers/switches are vertices; network links are edges. Routing protocols use graph algorithms to find best paths.

Flight Networks

Airports are vertices; flights are weighted edges (cost, duration). Used for finding cheapest/fastest routes.

Recommendation Systems

Users and items are vertices; interactions are edges. Collaborative filtering traverses user-item graphs.

Web Page Linking

Web pages are vertices; hyperlinks are directed edges. Google's PageRank models the web as a massive directed graph.

Dependency Graphs

Packages/tasks are vertices; dependencies are directed edges. Package managers and build systems use DAGs to determine order.

Graph Representation

Adjacency Matrix

A V x V matrix where adj[i][j] = 1 (or weight) if edge (i,j) exists, else 0. Simple and fast for edge existence checks.

Space: O(V^2) — wasteful for sparse graphs. Check edge: O(1). Add edge: O(1). Neighbors: O(V) to scan entire row.

Adjacency List

An array of lists where adj[i] stores all neighbors of vertex i. The most common and efficient representation for sparse graphs.

Space: O(V + E). Check edge: O(degree(v)). Add edge: O(1). Neighbors: O(degree(v)).

Adjacency Matrix (Undirected)

Symmetric matrix. Diagonal = 0 (no self-loops). Space: O(V^2) = O(25) for V=5.

Adjacency List

0 → [1, 2]
1 → [0, 2]
2 → [0, 1, 3]
3 → [2, 4]
4 → [3]

Each vertex stores only its neighbors. Space: O(V + E) = O(5 + 6) = O(11). Much more efficient for sparse graphs.

Edge List

(0, 1)
(0, 2)
(1, 2)
(2, 3)
(3, 4)

Simple list of all edges. Space: O(E). Good for Kruskal's MST (sort edges by weight). Slow for neighbor lookup.

Representation choice matters: For sparse graphs (E ~ V), adjacency list uses O(V + E) vs matrix O(V^2). For dense graphs (E ~ V^2), the matrix can be faster due to cache locality. Most real-world graphs are sparse — adjacency list is the default choice.

Internal Working Visualization

Graph structure — nodes, edges, and relationships

1Nodes (Vertices): The fundamental data points. Each node can store a value, color, or any payload. In C++, often represented as indices 0 to V-1.

2Edges: Connections between nodes. Undirected edges are bidirectional; directed edges have a specific direction from source to destination.

3Neighbors: All vertices directly reachable from a given vertex via one edge. In adjacency list: adj[u] contains all neighbors of u.

4Degree: For undirected: count of edges incident to a vertex. For directed: Indegree (incoming edges) + Outdegree (outgoing edges) = total degree.

5Path & Cycle: A path is a sequence of connected vertices. A cycle is a path that starts and ends at the same vertex. Self-loops (u,u) and parallel edges (multiple edges between same pair) are special cases.

6Connected Components: Maximal subgraphs where every pair of vertices is connected by a path. A disconnected graph has multiple components.

Complexity Summary

Adjacency Matrix Space

O(V^2)

Fixed VxV matrix regardless of edge count. Wasteful for sparse graphs.

Adjacency List Space

O(V + E)

Only stores existing edges. Optimal for sparse real-world graphs.

Add Edge

O(1)

Push to adjacency list or set matrix cell. Both are constant time.

Remove Edge

O(V) / O(E)

Matrix: O(1) to clear cell. List: O(degree) to find and erase from vector.

Check Edge Exists

O(1) / O(V)

Matrix: direct lookup O(1). List: scan neighbors O(degree), worst O(V).

Traverse Graph (BFS/DFS)

O(V + E)

Visit every vertex and edge exactly once with adjacency list.

BFS Time

O(V + E)

Each vertex enqueued once, each edge examined once. Queue operations O(1).

DFS Time

O(V + E)

Each vertex visited once, each edge examined once. Recursion stack O(V).

BFS Space

O(V)

Queue holds at most V vertices. Visited array of size V. Total O(V).

Graph Types

Undirected Graph

Edges have no direction. If (u,v) exists, traversal is possible both ways. Symmetric adjacency matrix.

Use: Social networks, road maps, molecular structures

Space: O(V + E)

Directed Graph

Edges have direction u → v. Not necessarily symmetric. Strongly connected if path exists both ways for all pairs.

Use: Web pages, dependency graphs, one-way streets

Space: O(V + E)

Weighted Graph

Each edge has a weight/cost. Can be directed or undirected. Adjacency list stores (neighbor, weight) pairs.

Use: GPS routing, network bandwidth, flight costs

Space: O(V + E)

Unweighted Graph

All edges have equal weight (implicitly 1). BFS finds shortest path by edge count. Simpler to implement.

Use: Maze solving, social reach, web crawling

Space: O(V + E)

DAG

Directed Acyclic Graph — no directed cycles. Essential for topological sorting. Every DAG has at least one topological order.

Use: Task scheduling, expression trees, build systems

Detect cycle: O(V + E)

Tree

Connected acyclic undirected graph with exactly V-1 edges. Has a unique simple path between any two vertices.

Use: File systems, DOM, hierarchical data, MST results

Edges: always V - 1

Forest

A collection of disjoint trees. Disconnected acyclic undirected graph. Each component is a tree.

Use: Disjoint sets, hierarchical clustering

Components: each is a tree

Complete Graph

Every pair of distinct vertices is connected by a unique edge. K_n has n(n-1)/2 edges (undirected).

Use: Tournament scheduling, fully connected networks

Edges: V(V-1)/2

Bipartite Graph

Vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.

Use: Matching problems, job assignment, chessboard coloring

Check: BFS with two colors O(V+E)

Cyclic Graph

Contains at least one cycle. Can be directed or undirected. Cycle detection is a fundamental graph problem.

Use: Deadlock detection, currency arbitrage, game theory

Detect: O(V + E)

Acyclic Graph

Contains no cycles. Undirected acyclic = forest. Directed acyclic = DAG. Simpler algorithms often apply.

Use: Expression evaluation, Bayesian networks

Tree is always acyclic

Connected Graph

A path exists between every pair of vertices. For directed: strongly connected requires paths in both directions.

Use: Network reliability, communication networks

Check: BFS/DFS from any node O(V+E)

Graph Traversal Theory

Breadth First Search (BFS)

Explores vertices level by level, starting from a source node. Uses a Queue (FIFO) to track which node to visit next.

BFS finds the shortest path in an unweighted graph because it explores all nodes at distance k before any node at distance k+1.

// BFS pseudocode
queue q; q.push(src);
visited[src] = true;
while (!q.empty()) {
  u = q.front(); q.pop();
  for (v : adj[u])
    if (!visited[v])
      visited[v] = true, q.push(v);
}

Depth First Search (DFS)

Explores as deep as possible along each branch before backtracking. Uses a Stack (or recursion) to track the path.

DFS is simpler to implement recursively and is ideal for cycle detection, topological sort, and connected components.

// DFS pseudocode
void dfs(int u) {
  visited[u] = true;
  for (v : adj[u])
    if (!visited[v])
      dfs(v);
}
// Call: dfs(src);

Why BFS uses Queue, DFS uses Stack: BFS needs to explore all neighbors at the current depth before going deeper — FIFO order ensures this. DFS needs to go as deep as possible before exploring siblings — LIFO order (stack) naturally supports this backtracking behavior. Recursion implicitly uses the call stack.

BFS vs DFS Comparison

Aspect	BFS	DFS
Traversal Structure	Level by level (breadth-first)	Deep as possible (depth-first)
Data Structure	Queue (FIFO)	Stack (LIFO) or Recursion
Shortest Path (unweighted)	Finds shortest path	Does not guarantee shortest
Memory Usage	O(V) — queue holds frontier	O(V) — recursion stack
Implementation	Iterative with queue	Recursive or iterative with stack
Applications	Shortest path, level-order, bipartite check	Cycle detection, topo sort, SCC, maze
Time Complexity	O(V + E)	O(V + E)
Space Complexity	O(V)	O(V)
Advantages	Optimal for shortest path; natural level order	Simpler code; less memory for deep graphs
Disadvantages	More memory for wide graphs	Can overflow stack on deep graphs; no shortest path

Example Scenarios

Interactive Graph Visualization

Unvisited Current Processing Visited Back Edge (Cycle)

Waiting to start

Data Structure State

Current operation details

Current Node

—

Operation

—

Distance

—

Visited

nodes

Current

—

active node

Queue/Stack

pending nodes

Edges

examined

Step — of —

Select an example scenario, or use the manual controls below, then press Play.

Manual controls — build your own graph traversal

Done

Speed Medium

Step-by-step traversal log

Step	Current Node	Visited Set	Queue/Stack	Parent	Traversal Order	Action

Graph Applications

Google Maps Routing

Roads as edges, intersections as vertices. Dijkstra and A* find shortest/fastest routes in real-time using weighted directed graphs.

Social Networks

Friend recommendation via mutual friends (common neighbors), influence propagation, and community detection using graph clustering.

Web Crawlers

The entire web is a directed graph. Crawlers use BFS/DFS to discover pages, and PageRank uses the graph structure for ranking.

Recommendation Engines

User-item bipartite graphs enable collaborative filtering. "Users who bought X also bought Y" traverses the graph to find similar items.

Network Routing

OSPF and BGP protocols model the internet as a graph. Shortest path algorithms determine optimal packet forwarding paths.

Compiler Dependencies

Source files and headers form a DAG. Topological sort determines compilation order so dependencies are built before dependents.

AI Knowledge Graphs

Entities and relationships form graphs powering question answering, semantic search, and reasoning in modern LLM systems.

Game Pathfinding

Game maps are grid graphs. A* search with heuristics finds optimal paths for NPCs while avoiding obstacles in real-time.

Operating Systems

Resource allocation graphs detect deadlocks. If a cycle exists in the wait-for graph, the system is in a deadlock state.

Advantages & Disadvantages

Advantages

Models real-world relationships naturally and flexibly.
Extremely versatile structure supporting many algorithms.
Powerful representation for networks, maps, and dependencies.
Foundation of advanced DSA: shortest path, MST, flow, matching.
Adjacency list provides O(1) edge addition and O(V+E) traversal.
Graph databases (Neo4j) scale relationship queries efficiently.

Disadvantages

Can become memory intensive for dense graphs (O(V^2) matrix).
Many graph algorithms have high theoretical complexity.
Difficult visualization and debugging for huge graphs.
Dense graph storage overhead with adjacency matrix.
Cycle detection and pathfinding can be computationally expensive.
Recursive DFS risks stack overflow on deep graphs.

C++ STL Graph Implementation

graph_adjlist.cpp · Adjacency List

#include <bits/stdc++.h>
using namespace std;

// Adjacency List representation (most common)
int main() {
    int V = 5, E = 4;
    vector<vector<int>> adj(V);

    // Undirected graph: add edge both ways
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);
    adj[2].push_back(3); adj[3].push_back(2);

    // Print adjacency list
    for (int i = 0; i < V; i++) {
        cout << i << " -> ";
        for (int v : adj[i]) cout << v << " ";
        cout << "\n";
    }
    return 0;
}

graph_adjmatrix.cpp · Adjacency Matrix

#include <bits/stdc++.h>
using namespace std;

// Adjacency Matrix representation
int main() {
    int V = 5;
    vector<vector<int>> adj(V, vector<int>(V, 0));

    // Add edges (undirected)
    adj[0][1] = adj[1][0] = 1;
    adj[0][2] = adj[2][0] = 1;
    adj[1][2] = adj[2][1] = 1;
    adj[2][3] = adj[3][2] = 1;

    // Check if edge (0,1) exists: O(1)
    if (adj[0][1]) cout << "Edge exists\n";
    return 0;
}

bfs.cpp · Breadth First Search

#include <bits/stdc++.h>
using namespace std;

void bfs(int src, vector<vector<int>>& adj) {
    int V = adj.size();
    vector<bool> visited(V, false);
    vector<int> dist(V, -1);
    queue<int> q;

    visited[src] = true;
    dist[src] = 0;
    q.push(src);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

dfs.cpp · Depth First Search

#include <bits/stdc++.h>
using namespace std;

void dfs(int u, vector<vector<int>>& adj,
         vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u])
        if (!visited[v])
            dfs(v, adj, visited);
}

// Iterative DFS using explicit stack
void dfsIterative(int src, vector<vector<int>>& adj) {
    int V = adj.size();
    vector<bool> visited(V, false);
    stack<int> st;
    st.push(src);

    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        cout << u << " ";
        for (int v : adj[u])
            if (!visited[v]) st.push(v);
    }
}

connected_components.cpp · Connected Components

#include <bits/stdc++.h>
using namespace std;

void dfs(int u, vector<vector<int>>& adj,
         vector<bool>& vis, vector<int>& comp) {
    vis[u] = true;
    comp.push_back(u);
    for (int v : adj[u])
        if (!vis[v]) dfs(v, adj, vis, comp);
}

int countComponents(vector<vector<int>>& adj) {
    int V = adj.size(), count = 0;
    vector<bool> vis(V, false);
    for (int i = 0; i < V; i++) {
        if (!vis[i]) {
            vector<int> comp;
            dfs(i, adj, vis, comp);
            count++;
            // comp now holds one connected component
        }
    }
    return count;  // number of components
}

cycle_detection.cpp · Cycle Detection (Undirected)

#include <bits/stdc++.h>
using namespace std;

bool hasCycle(int u, int parent,
              vector<vector<int>>& adj,
              vector<bool>& vis) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) {
            if (hasCycle(v, u, adj, vis))
                return true;
        } else if (v != parent)
            return true;  // back edge found
    }
    return false;
}

weighted_graph.cpp · Weighted Graph (Dijkstra)

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

// Dijkstra: shortest path in weighted graph
vector<int> dijkstra(int src,
    vector<vector<pii>>& adj) {
    int V = adj.size();
    vector<int> dist(V, INT_MAX);
    priority_queue<pii, vector<pii>,
                   greater<pii>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto& [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
    }
    return dist;
}

// Weighted adjacency list: adj[u].push_back({v, weight})

Graph Algorithms Overview

BFS

Level-order traversal. Finds shortest path in unweighted graphs.

Time: O(V+E) | Space: O(V)

Social reach, web crawling, bipartite check

DFS

Deep traversal. Detects cycles, finds connected components.

Time: O(V+E) | Space: O(V)

Topo sort, maze solving, SCC (Kosaraju/Tarjan)

Dijkstra

Shortest path from source to all vertices. Greedy approach.

Time: O((V+E)logV) | Space: O(V)

GPS routing, network routing, game AI

Bellman-Ford

Shortest path with negative weights. Detects negative cycles.

Time: O(VE) | Space: O(V)

Currency arbitrage, network flow with costs

Floyd-Warshall

All-pairs shortest path. Dynamic programming approach.

Time: O(V^3) | Space: O(V^2)

Transitive closure, network diameter

Topological Sort

Linear ordering of DAG vertices respecting dependencies.

Time: O(V+E) | Space: O(V)

Task scheduling, course prerequisites, build systems

Kruskal

Minimum Spanning Tree using Union-Find. Sorts edges by weight.

Time: O(E log E) | Space: O(V)

Network design, clustering, approximate TSP

Prim

Minimum Spanning Tree using priority queue. Grows tree from source.

Time: O((V+E)logV) | Space: O(V)

Network design, road construction, clustering

Union Find

Disjoint Set Union with path compression and union by rank.

Time: O(alpha(V)) ~ O(1) | Space: O(V)

Kruskal, cycle detection, connected components

Kosaraju

Finds strongly connected components in directed graphs.

Time: O(V+E) | Space: O(V)

Social circles, web page groups, 2-SAT

Tarjan

Single-pass SCC algorithm using low-link values. More efficient.

Time: O(V+E) | Space: O(V)

SCC, articulation points, bridges

Ask AI — Graph Theory

Ask AI — Explain any Graph concept

Ask a question above to get an AI explanation of any Graph Theory concept.

Interview Preparation

Detect cycle in an undirected graph

Use DFS with a parent parameter. If you visit a node that is already visited and is NOT the parent, a cycle exists. Time: O(V+E).

Cycle

Find shortest path in unweighted graph

BFS naturally finds the shortest path by edge count. Maintain a distance array updated when each node is first visited. Time: O(V+E).

BFS

Number of islands (connected components)

Traverse the grid. When you find an unvisited land cell, run DFS/BFS to mark the entire island. Increment count. Time: O(V+E) = O(m*n).

DFS

Topological sort of a DAG

Use DFS: push node to stack after exploring all neighbors. Reverse the stack. Or use Kahn's algorithm: repeatedly remove nodes with indegree 0. Time: O(V+E).

Topo Sort

Check if graph is bipartite

Use BFS with two colors. Start coloring from any node. If you find a neighbor with the same color, the graph is not bipartite. Time: O(V+E).

BFS

Clone a graph (deep copy)

Use DFS/BFS with a hash map to track cloned nodes. For each original node, create a clone if not exists, then recursively clone neighbors. Time: O(V+E).

DFS

Find all paths from source to target

Use DFS with backtracking. Maintain a current path list. When target is reached, add path to results. Backtrack by removing the last node. Time: O(2^V) worst case.

DFS

Word ladder (shortest transformation)

Model as a graph where edges connect words differing by one letter. Use BFS from beginWord to find shortest path to endWord. Time: O(N * L^2 * 26).

BFS

Course schedule (prerequisites)

Build a directed graph of courses and prerequisites. Use topological sort (Kahn's or DFS). If all courses can be ordered, return true. Detect cycle = impossible.

Topo Sort

Critical connections (bridges)

Use Tarjan's algorithm. Track discovery times and low-link values. An edge (u,v) is a bridge if low[v] > disc[u]. Time: O(V+E).

DFS

Key Takeaways

📈

Graph fundamentals: A graph G=(V,E) models pairwise relationships. Vertices are entities, edges are connections. Understanding directed vs undirected, weighted vs unweighted is essential.

📝

Representations: Adjacency list (O(V+E)) is preferred for sparse graphs. Adjacency matrix (O(V^2)) works for dense graphs or when fast edge lookup is needed. Edge list is best for Kruskal.

🚀

Traversals: BFS uses a queue for level-order exploration and shortest paths in unweighted graphs. DFS uses recursion/stack for deep exploration, cycle detection, and topological sort. Both are O(V+E).

⏱

Complexities: Most graph algorithms run in O(V+E) time with O(V) space. Dijkstra is O((V+E)logV). Floyd-Warshall is O(V^3). Always choose the right algorithm for the graph type.

🌟

Algorithms: Master BFS, DFS, Dijkstra, topological sort, and Union-Find. These form the foundation for solving 80% of graph interview problems. Understand when to apply each.

💼

Interview importance: Graph problems are extremely common in FAANG interviews. Practice detecting cycles, finding shortest paths, topological sorting, and connected components. These are the building blocks.