Module 11 : Graphs

A graph is a collection of nodes (vertices) connected by edges.
Graphs model real-world relationships:

• Social networks
• Road maps
• Computer networks
• Dependency systems
• Recommendation engines

If trees are about hierarchy, graphs are about relationships.

Graph Representation

Choosing the right representation affects performance and clarity.

Adjacency List

Each node stores a list of its neighbors.

List<List<Integer>> graph = new ArrayList<>();
for(int i = 0; i < n; i++)
    graph.add(new ArrayList<>());

graph.get(0).add(1);
graph.get(1).add(0); // undirected

Pros

• Space efficient: O(V + E)
• Fast traversal

Cons

• Edge lookup is slower

Used in most interview problems.

Adjacency Matrix

2D matrix where:

matrix[i][j] = 1 → edge exists

int[][] matrix = new int[n][n];
matrix[0][1] = 1;

Pros

• Fast edge lookup

Cons

• Space heavy: O(V²)

Used in dense graphs and Floyd-Warshall.

BFS (Breadth First Search)

BFS explores nodes level by level using a queue.

Use cases

• Shortest path in unweighted graph
• Level order traversal
• Grid problems

void bfs(int start){
    Queue<Integer> q = new LinkedList<>();
    boolean[] vis = new boolean[n];

    q.add(start);
    vis[start] = true;

    while(!q.isEmpty()){
        int node = q.poll();
        for(int nei : graph.get(node)){
            if(!vis[nei]){
                vis[nei] = true;
                q.add(nei);
            }
        }
    }
}

Time: O(V + E)

DFS (Depth First Search)

DFS explores as deep as possible before backtracking.

Use cases

• Cycle detection
• Connected components
• Topological sort

void dfs(int node){
    vis[node] = true;
    for(int nei : graph.get(node)){
        if(!vis[nei])
            dfs(nei);
    }
}

Connected Components

Problem

Count separate subgraphs.

Approach

• Run DFS/BFS from every unvisited node
• Each run = one component

int components = 0;
for(int i = 0; i < n; i++){
    if(!vis[i]){
        dfs(i);
        components++;
    }
}

Cycle Detection

Undirected Graph (DFS)

Idea:

• Track parent
• If visited neighbor ≠ parent → cycle

boolean dfs(int node, int parent){
    vis[node] = true;
    for(int nei : graph.get(node)){
        if(!vis[nei]){
            if(dfs(nei, node)) return true;
        } else if(nei != parent){
            return true;
        }
    }
    return false;
}

Directed Graph (DFS + recursion stack)

Idea:

• Maintain recursion stack
• Back edge → cycle

boolean dfs(int node){
    vis[node] = true;
    stack[node] = true;

    for(int nei : graph.get(node)){
        if(!vis[nei] && dfs(nei)) return true;
        else if(stack[nei]) return true;
    }

    stack[node] = false;
    return false;
}

Topological Sort

What is Topological Sort?

Linear ordering of nodes such that:

u → v  ⇒  u comes before v

Only works for DAG.

Kahn’s Algorithm (BFS)

Queue<Integer> q = new LinkedList<>();
int[] indeg = new int[n];

for(each edge u→v)
    indeg[v]++;

for(int i = 0; i < n; i++)
    if(indeg[i] == 0) q.add(i);

while(!q.isEmpty()){
    int node = q.poll();
    for(int nei : graph.get(node)){
        indeg[nei]--;
        if(indeg[nei] == 0)
            q.add(nei);
    }
}

---

Shortest Path Algorithms

---

Dijkstra’s Algorithm

Find shortest path from source to all nodes
Only works with non-negative weights

PriorityQueue<int[]> pq = new PriorityQueue<>(
    (a, b) -> a[1] - b[1]
);

pq.add(new int[]{src, 0});
dist[src] = 0;

while(!pq.isEmpty()){
    int[] cur = pq.poll();
    int node = cur[0], d = cur[1];

    for(Edge e : graph[node]){
        if(dist[e.to] > d + e.wt){
            dist[e.to] = d + e.wt;
            pq.add(new int[]{e.to, dist[e.to]});
        }
    }
}

Time: O(E log V)

---

Bellman-Ford Algorithm

Handles negative weights
Detects negative cycles

for(int i = 1; i < V; i++){
    for(Edge e : edges){
        if(dist[e.u] + e.wt < dist[e.v])
            dist[e.v] = dist[e.u] + e.wt;
    }
}

Extra iteration checks for negative cycles.

Time: O(VE)

---

Floyd-Warshall Algorithm

All-pairs shortest path
Uses DP

for(int k = 0; k < n; k++)
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        dist[i][j] = Math.min(dist[i][j], 
                              dist[i][k] + dist[k][j]);

Time: O(n³)

---

Minimum Spanning Tree (MST)

A tree that:

• Connects all vertices
• Has minimum total edge weight
• Contains V-1 edges

---

Prim’s Algorithm

Grows MST from a node
Uses Min Heap

PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(0, 0));

while(!pq.isEmpty()){
    Edge e = pq.poll();
    if(vis[e.to]) continue;
    vis[e.to] = true;

    for(Edge next : graph[e.to])
        if(!vis[next.to])
            pq.add(next);
}

---

Kruskal’s Algorithm

Sorts edges by weight
Uses Union-Find

Collections.sort(edges);

for(Edge e : edges){
    if(find(e.u) != find(e.v)){
        union(e.u, e.v);
        mst += e.wt;
    }
}

---

Union-Find (DSU)

Used to track components efficiently.

Operations

• Find
• Union

int find(int x){
    if(parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void union(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b)
        parent[b] = a;
}

With path compression → almost O(1)

---

Bipartite Graph

Graph that can be colored with 2 colors
No adjacent nodes share same color.

Check using BFS

Queue<Integer> q = new LinkedList<>();
color[start] = 0;

while(!q.isEmpty()){
    int node = q.poll();
    for(int nei : graph.get(node)){
        if(color[nei] == -1){
            color[nei] = 1 - color[node];
            q.add(nei);
        } else if(color[nei] == color[node])
            return false;
    }
}

---

Grid-Based Graph Problems

Grid problems are hidden graphs.

Example

• Number of islands
• Shortest path in maze
• Rotting oranges

---

DFS on Grid (Islands)

void dfs(int r, int c){
    if(outOfBounds or grid[r][c] == 0) return;
    grid[r][c] = 0;
    dfs(r+1,c);
    dfs(r-1,c);
    dfs(r,c+1);
    dfs(r,c-1);
}

---

BFS on Grid (Shortest Path)

Use queue with directions.

int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};