Graph Basics

Graph is a data structure consisting of Vertices/Nodes and Edges used to represent relationships between things.

Components of a Graph

• Vertex (V) or Node: A point in the graph
• Edge (E): A connection between two vertices

Types of Graphs

Type	Description
Undirected	Edges have no direction (bidirectional)
Directed	Edges have direction (one-way)
Weighted	Edges have weights/costs
Unweighted	Edges have no weights
Simple	No self-loops and multiple edges
Connected	There’s a path connecting all vertices
Tree	Connected graph with no cycles
DAG	Directed Acyclic Graph

Storing Graph Data

1. Adjacency Matrix

Store as 2D array of size $V \times V$

int n = 5; // number of vertices
vector<vector<int>> adj(n, vector<int>(n, 0));

// Add edge (u, v)
void addEdge(int u, int v) {
    adj[u][v] = 1;
    adj[v][u] = 1; // for undirected graph
}

// Check if edge (u, v) exists
bool hasEdge(int u, int v) {
    return adj[u][v] != 0;
}

Pros:

• Edge lookup takes $O(1)$
• Suitable for Dense Graphs

Cons:

• Uses $O(V^2)$ memory
• Not suitable for Sparse Graphs

2. Adjacency List (Recommended)

Store list of neighbors for each vertex

int n = 5;
vector<vector<int>> adj(n);

// Add edge (u, v)
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u); // for undirected graph
}

// Weighted graph
vector<vector<pair<int, int>>> adjW(n);

void addWeightedEdge(int u, int v, int w) {
    adjW[u].push_back({v, w});
    adjW[v].push_back({u, w});
}

Pros:

• Uses $O(V + E)$ memory
• Suitable for Sparse Graphs (most common in competitions)

Cons:

• Edge lookup takes $O(degree)$ time

3. Edge List

Store list of all edges

struct Edge {
    int u, v, w; // from, to, weight
};

vector<Edge> edges;

void addEdge(int u, int v, int w) {
    edges.push_back({u, v, w});
}

Used for:

• Algorithms that need sorted edges (Kruskal’s MST)
• Bellman-Ford Algorithm

Input Reading

Undirected Unweighted Graph

5 6
1 2
1 3
2 3
2 4
3 5
4 5

int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

Directed Weighted Graph

5 6
1 2 10
1 3 5
2 3 2
2 4 1
3 5 7
4 5 4

int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> adj(n + 1);

for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    // adj[v].push_back({u, w}); // if undirected
}

Important Terminology

Degree

Number of edges connected to a vertex

// Undirected graph
int degree(int v) {
    return adj[v].size();
}

// Directed graph
int inDegree[n], outDegree[n];

for (int u = 0; u < n; u++) {
    for (int v : adj[u]) {
        outDegree[u]++;
        inDegree[v]++;
    }
}

Path & Walk

• Walk: Sequence of vertices where adjacent ones are connected by edges
• Path: Walk that doesn’t visit any vertex twice
• Cycle: Path that starts and ends at the same vertex

Connected Components

Groups of vertices that have paths connecting them

vector<bool> visited(n + 1, false);
int components = 0;

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

// Count connected components
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        dfs(i);
        components++;
    }
}

Special Graph Types

Tree

A graph where:

• Has $n$ vertices and $n-1$ edges
• Connected and has no cycles
• Has unique path between every pair of vertices

// Tree will have edges = vertices - 1
bool isTree(int n, int m) {
    if (m != n - 1) return false;
    // Check if connected
    dfs(1);
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) return false;
    }
    return true;
}

Bipartite Graph

Graph where vertices can be divided into 2 groups, with edges only between groups

vector<int> color(n + 1, -1);

bool isBipartite(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (color[v] == -1) {
                color[v] = 1 - color[u];
                q.push(v);
            } else if (color[v] == color[u]) {
                return false; // has odd cycle
            }
        }
    }
    return true;
}

DAG (Directed Acyclic Graph)

Directed graph with no cycles

Used in:

• Topological Sort
• Dynamic Programming on DAG
• Dependency Resolution

Handshaking Lemma

Sum of all degrees = 2 × number of edges

$\sum_{v \in V} deg(v) = 2|E|$

Summary

Storage Method	Memory	Check Edge	Add Edge	Use Case
Adj Matrix	$O(V^2)$	$O(1)$	$O(1)$	Dense Graph
Adj List	$O(V+E)$	$O(deg)$	$O(1)$	Sparse Graph
Edge List	$O(E)$	$O(E)$	$O(1)$	Kruskal’s, Bellman-Ford

💡 Tip: Most competition problems use Adjacency List because graphs are usually sparse.