Data Structures and Algorithms in C (DSA)

📘 Chapter: Graph Representations (Adjacency Matrix & List)

Welcome to the realm of graphs! A graph is a fundamental, non-linear data structure that consists of a set of interconnected entities. Think of it as a network of points (or nodes) linked together by lines (or edges). Graphs are everywhere in the real world: social networks, road maps, the internet, airline routes, and even dependencies between tasks in a project.

🤔 What are Graphs? Key Terminology

• Vertex (Node): A fundamental entity or point in the graph. (e.g., a city on a map, a person in a social network).
• Edge: A connection or link between two vertices. (e.g., a road between two cities, a friendship between two people).
• Directed Graph (Digraph): Edges have a direction. If an edge goes from A to B, it doesn't necessarily mean there's an edge from B to A. (e.g., one-way streets, Twitter followers).
• Undirected Graph: Edges have no direction. If an edge connects A and B, it means A is connected to B, and B is connected to A. (e.g., two-way roads, Facebook friends).
• Weighted Graph: Edges have a value (weight) associated with them, representing cost, distance, time, etc. (e.g., distance on a road map, cost of a flight).
• Unweighted Graph: Edges have no associated value; they simply represent a connection.
• Path: A sequence of vertices connected by edges.
• Cycle: A path that starts and ends at the same vertex.
• Degree: The number of edges connected to a vertex. In a directed graph, it's divided into in-degree (incoming edges) and out-degree (outgoing edges).

To apply algorithms to graphs, we first need a systematic way to store them in computer memory. The two most common ways are **Adjacency Matrix** and **Adjacency List**.

📊 1. Adjacency Matrix

An Adjacency Matrix represents a graph as a 2D array (or matrix) of size $V \times V$, where $V$ is the number of vertices.

• If there's an edge between vertex `i` and vertex `j`, then `matrix[i][j]` is typically set to `1` (for unweighted graphs) or the edge's `weight` (for weighted graphs).
• If there's no edge, `matrix[i][j]` is `0` (or `infinity` for weighted graphs, if using for shortest paths).
• For an undirected graph, the matrix is symmetric (`matrix[i][j] == matrix[j][i]`). For a directed graph, it may not be.

Adjacency Matrix Visualization

Adjacency Matrix Pros & Cons:

• Pros:
  • $O(1)$ edge checking: To check if an edge exists between two vertices $(i, j)$, simply look up `matrix[i][j]`.
  • Easy to add/remove edges (just flip a bit/value).
• Cons:
  • $O(V^2)$ space: Always requires $V^2$ space, even for graphs with very few edges (sparse graphs), leading to wasted memory.
  • $O(V)$ to find all neighbors: To find all neighbors of a vertex `i`, you must iterate through the entire row `i`.

// Conceptual C++ for Adjacency Matrix
const int MAX_VERTICES = 100;
int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // For unweighted graph

// Initialize (all 0s)
void init_matrix(int V) {
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            adjMatrix[i][j] = 0;
        }
    }
}

// Add an undirected edge
void add_edge_matrix(int u, int v) {
    adjMatrix[u][v] = 1;
    adjMatrix[v][u] = 1; // For undirected
}

// Check if edge exists
bool has_edge_matrix(int u, int v) {
    return adjMatrix[u][v] == 1;
}
  

📚 2. Adjacency List

An Adjacency List represents a graph as an array of lists (or vectors in C++, ArrayLists in Java, etc.). The size of the array is $V$.

• Each index `i` in the array represents a vertex `i`.
• `adjList[i]` contains a list of all vertices that are adjacent to vertex `i` (i.e., neighbors of `i`).
• For weighted graphs, the list stores pairs `(neighbor, weight)`.

Adjacency List Visualization

Adjacency List Pros & Cons:

• Pros:
  • $O(V + E)$ space: Uses space proportional to the number of vertices and edges, which is very efficient for sparse graphs (graphs with few edges relative to $V^2$).
  • $O(\text{degree}(V))$ to find all neighbors: Efficiently iterate through all neighbors of a vertex `i`.
• Cons:
  • $O(\text{degree}(V))$ edge checking: To check if an edge exists between $(i, j)$, you might need to iterate through the list of `i`'s neighbors. For a graph with `E` edges and `V` vertices, average is $O(E/V)$, worst case $O(V)$.

// Conceptual C++ for Adjacency List
const int MAX_VERTICES_AL = 100;
vector<int> adjList[MAX_VERTICES_AL]; // Array of vectors for unweighted

// Add an undirected edge
void add_edge_list(int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u); // For undirected
}

// Check if edge exists (less efficient than matrix)
bool has_edge_list(int u, int v) {
    for (int neighbor : adjList[u]) {
        if (neighbor == v) return true;
    }
    return false;
}
  

⚖️ Adjacency Matrix vs. Adjacency List: A Comparison

Choosing between them depends on the graph's density (how many edges it has relative to the maximum possible) and the types of operations you'll perform most frequently. For competitive programming, Adjacency List is generally preferred because most graphs given are sparse.

📌 Real-Life Example (UdaanPath)

Graphs are fundamental to how a platform like UdaanPath might manage and process relationships:

• Course Prerequisites: A graph can represent which courses must be completed before others. Each course is a vertex, and a directed edge from Course A to Course B means A is a prerequisite for B. This helps in validating student enrollments and suggesting learning paths.
• Skill Dependencies: Similar to courses, skills can have prerequisites. A graph defines the skill tree, ensuring users acquire foundational skills before advanced ones.
• Content Recommendation Network: Based on user interactions (likes, views, enrollments), a graph can be built where users and content items are vertices, and edges represent interactions. This graph can then be traversed to recommend similar content or connect users with similar interests.
• Social Learning Network: Representing connections between students (e.g., study groups, peer mentoring). This graph allows for identifying communities, recommending study partners, or understanding information flow.
• API Microservices Dependencies: In a complex backend system, microservices can be vertices, and an edge represents one service calling another. This graph is crucial for understanding system architecture, identifying bottlenecks, and debugging.

✅ Summary: The Blueprint for Graph Algorithms

• Graphs model relationships between entities (vertices) using connections (edges).
• Key terms include Directed/Undirected, Weighted/Unweighted, Path, Cycle, Degree.
• Adjacency Matrix: $V \times V$ 2D array. $O(V^2)$ space, $O(1)$ edge check, $O(V)$ to find neighbors. Best for dense graphs.
• Adjacency List: Array of lists. $O(V + E)$ space, $O(\text{degree}(u))$ edge check, $O(\text{degree}(u))$ to find neighbors. Best for sparse graphs.
• Choosing the right representation is crucial for the efficiency of graph algorithms.

📤 Coming Next: BFS and DFS (Traversal & Search)

Now that we know how to store graphs, it's time to learn how to explore them! Our next chapter will delve into the two most fundamental graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). These algorithms are the backbone for solving countless graph problems.