Graph Algorithms

Graph Algorithms: Navigating Complex Networks

Graphs represent the absolute pinnacle of data structure interview questions for top-tier tech companies. Why? Because the modern digital world runs entirely on graph networks. When you search for the fastest route on Google Maps, you traverse a graph of cities and roads. When you view friends on Facebook or connections on LinkedIn, you query a graph of users. Even the underlying architecture of Git commits, internet routers, and microservice dependencies rely purely on graph theory.

1. What is a Graph?

A graph abandons the strict top-down hierarchy of a Tree. Instead, it forms a free-flowing network built from two core components:

• Vertices (Nodes): The actual data points in the network (e.g., specific cities, or specific users).
• Edges: The physical or logical connections linking those nodes together (e.g., the highways between cities).

Graph Terminology & Types

To manipulate graphs efficiently, you must understand the language used to describe their physical structures.

• Degree: The total number of edges connected directly to a single vertex.
• Undirected Graph: The connections act like two-way streets. If Node A connects to Node B, you can travel backward from B to A freely. (Example: A mutual Facebook friendship).
• Directed Graph (Digraph): The connections act like one-way streets. Node A points to Node B, but you cannot travel backward. (Example: An Instagram follower).
• Weighted Graph: The edges carry a specific mathematical "cost" or "distance." Traveling from A to B might cost $5$, while A to C costs $2$. (Example: Traffic times on Google Maps).
• Cyclic vs. Acyclic: A Cyclic graph contains loops, meaning you can leave a node, follow a path, and eventually land right back on your starting node. An Acyclic graph contains zero loops.

2. Representing Graphs in Code

Computers do not visually "see" graphs. You must translate the network into a mathematical format the RAM can store. You achieve this using two primary methods.

Method 1: Adjacency Matrix

You create a massive 2D array (a grid). If an edge exists between Node A and Node B, you write a 1 in that exact cell; otherwise, you write a 0.

• Advantage: Instant, constant-time $O(1)$ lookup to verify if a specific edge exists.
• Disadvantage: It consumes an enormous $O(V^2)$ amount of memory. If a network has 10,000 users, you must build a grid of 100,000,000 cells, even if each user only has 2 friends.

Method 2: Adjacency List (Interview Preferred)

Instead of a massive grid, you create a simple array of lists. Each index represents a Node, and it strictly stores a dynamic list of only its direct neighbors.

• Why Interviewers Prefer It: It requires only $O(V + E)$ space. You only spend memory on the connections that physically exist, making it infinitely more efficient for sparse real-world networks.

---

3. BFS (Breadth-First Search)

Breadth-First Search radiates outward from a starting node like ripples in a pond. It explores the graph Level by Level. It visits all immediate neighbors first, then moves outward to the neighbors' neighbors.

To enforce this strict level-by-level rule, BFS utilizes a Queue (FIFO) data structure. The first node you discover is exactly the first node you process.

#include <stdio.h>
#define MAX 100

int graph[MAX][MAX];
int visited[MAX];

void BFS(int start, int vertices) {
    int queue[MAX];
    int front = 0, rear = 0;

    // Mark the start node and queue it
    visited[start] = 1;
    queue[rear++] = start;

    while(front < rear) {
        // Dequeue a node and print it
        int node = queue[front++];
        printf("%d ", node);

        // Find all unvisited neighbors and queue them
        for(int i = 0; i < vertices; i++) {
            if(graph[node][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

Time Complexity: $O(V + E)$ | Real-World Uses: Unweighted shortest path finding, peer-to-peer network broadcasting, and GPS routing algorithms.

---

4. DFS (Depth-First Search)

Depth-First Search acts like exploring a deep, dark cave system. It plunges as deep as physically possible down a single path. When it eventually hits a dead end, it backtracks to the previous intersection and tries a new route.

To enforce this deep-dive behavior, DFS utilizes a Stack (LIFO) data structure, which you can easily achieve using standard Recursion.

void DFS(int node, int vertices) {
    // Mark current node as visited
    visited[node] = 1;
    printf("%d ", node);

    // Recursively dive down into the first available unvisited neighbor
    for(int i = 0; i < vertices; i++) {
        if(graph[node][i] == 1 && !visited[i]) {
            DFS(i, vertices);
        }
    }
}

Feature	BFS	DFS
Data Structure Used	Queue	Stack (Recursion)
Traversal Style	Broad, Level-by-Level	Deep, Path-by-Path
Finds Shortest Path?	Yes (For unweighted graphs)	No
Memory Usage	Typically Higher	Typically Lower
Requires Backtracking?	No	Yes

---

5. Dijkstra's Algorithm (Shortest Path)

BFS easily finds the shortest path if all edges share the exact same weight. But what if roads have different speed limits? Dijkstra's Algorithm handles weighted graphs by tracking the absolute lowest cumulative distance to every node.

The Core Concept: Relaxation

Dijkstra relies entirely on a greedy mathematical step called Relaxation.
If your current best-known distance to Node B is $10$, but you discover a new route through Node A that reaches Node B in only $7$ steps, you "relax" the edge by updating your tracker to the new, superior $7$ distance.

By constantly parsing the network using a Priority Queue (Min-Heap) to process the closest unvisited nodes first, Dijkstra evaluates the shortest path in $O((V+E) \log V)$ time.

---

6. Floyd-Warshall Algorithm (All-Pairs Shortest Path)

Dijkstra only maps the distances outward from a single starting node. The Floyd-Warshall algorithm resolves the absolute shortest path between every single pair of nodes across the entire network simultaneously. It achieves this using a robust Dynamic Programming matrix.

The Core Formula

For every single pair of nodes ($i$ to $j$), it asks a simple question: "Is it faster to travel straight from $i$ to $j$, or is it faster to take a detour through intermediate node $k$?"

$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$

It executes this formula using a famous triple-nested loop structure, resulting in a time complexity of $O(V^3)$.

---

7. Topological Sort (Dependency Resolution)

Topological sorting is an absolute favorite for system design interviews. It applies strictly to Directed Acyclic Graphs (DAG). It outputs a linear ordering of vertices ensuring that if a dependency rule dictates "A must happen before B" ($A \rightarrow B$), Node A will unequivocally appear before Node B in the final list.

Real-world example: University course prerequisites. You cannot enroll in Microservices architecture until you successfully complete standard Java programming.

Kahn’s Algorithm (BFS Approach)

This technique uses an Indegree array. The Indegree represents how many incoming arrows point directly at a node. If a node has an Indegree of $0$, it possesses zero dependencies and can execute immediately.

• Step 1: Calculate the Indegree for every node. Push all nodes with an Indegree of $0$ into a Queue.
• Step 2: Dequeue a node and add it to your final sorted sequence.
• Step 3: For every neighbor of that node, subtract $1$ from their Indegree (representing a fulfilled dependency).
• Step 4: If a neighbor's Indegree drops to exactly $0$, push it into the Queue. Repeat until empty.

The Graph Interview Cheat Sheet

Memorize this mapping. When an interviewer asks a graph question, your required algorithm is highly predictable based on their prompt constraints:

Problem Requirement	The Algorithm to Use
Level-by-Level Analysis / Broadcasting	BFS (Breadth-First Search)
Path Existence / Maze Escapes / Deep Recursion	DFS (Depth-First Search)
Shortest Path (Unweighted Edges)	BFS
Shortest Path (Weighted, Positive Edges)	Dijkstra's Algorithm
Shortest Path Handling Negative Weights	Bellman-Ford Algorithm
Shortest Distance Between ALL Pairs	Floyd-Warshall Algorithm
Order Execution / Resolving Dependencies	Topological Sort
Connecting All Nodes with Absolute Minimum Cost	Minimum Spanning Tree (Kruskal/Prim)

The Golden Rules of Graph Problem Solving

Before writing a single line of code in an interview, explicitly clarify the environment with your interviewer by asking these core questions:

• Is the graph Directed or Undirected?
• Are the edges Weighted or Unweighted? (Can weights be negative?)
• Do we expect Cycles in the graph data?
• Do you need the optimal route from a Single Source or across All Pairs?

The answers to these four questions dictate your exact algorithmic approach instantly.