ReviseAlgo Logo

Graphs

Graph Fundamentals

Master Graph representation: vertices, edges, directed/undirected types, and Adjacency List vs Matrix implementations.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is a Graph?

A Graph is a non-linear data structure consisting of a finite set of Vertices (or Nodes) and a set of Edges connecting these vertices. Mathematically, G = (V, E).

Why study them?

Many real-world systems are networks of relationships. Graphs are used to model social networks, transportation routes, web page link maps, and dependency hierarchies. Mastering graph structures is essential to solve pathfinding, cycle detection, and scheduling algorithms.

Where is it Used?

  • Mapping Applications: Tracking roads (edges) connecting cities (vertices) for GPS route suggestions.
  • Social Media Networks: Representing users (vertices) and friendship links (edges) to suggest connections.

    • 2. Mental Model: Flight Connections Map

    Imagine looking at an airport display:

  • Vertices: The airports (e.g., JFK, LAX, LHR).
  • Edges: The direct flights flying between them.
  • Directed Graph: A flight goes from JFK to LHR, but there is no return flight.
  • Weighted Graph: The flight routes have distances or ticket prices associated with them.
  • Cycle: You can take a sequence of flights that starts at JFK, goes to LHR, then to LAX, and lands back at JFK.

    • 3. Graph Representations

    There are two primary methods to store a graph in code:

    1. Adjacency Matrix

    A 2D array of size V × V, where matrix[i][j] is 1 (or the edge weight) if there is an edge from vertex i to j, and 0 otherwise.
  • Space Complexity: O(V²)
  • Pros: O(1) time to check if an edge exists between two vertices.
  • Cons: Wasteful for sparse graphs (where E \ll V²), since most entries are 0.

    • 2. Adjacency List

    An array of lists of size V, where list[i] contains all the neighboring vertices of vertex i.
  • Space Complexity: O(V + E)
  • Pros: Memory efficient for sparse graphs. Easy to iterate over all neighbors of a vertex.
  • Cons: Checking if an edge exists between i and j takes O(degree(i)) time.

    • 4. Visual Comparison

    Given 3 vertices [0, 1, 2] with edges (0-1) and (1-2):

    Adjacency representations:

    5. Real-World Examples

  • Internet Link Maps: Web pages represent vertices, and hyperlinks between them represent directed edges (crawled by search engines like Google).
  • Package Managers: Package versions represent vertices, and package dependencies represent directed edges, used to install items in correct order.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test representation selection:
  • "Given a graph with 1,000,000 vertices and only 2,000,000 edges, how should you store it?" -> Answer: Use an Adjacency List. An Adjacency Matrix would require 10^12 elements, leading to a compilation out-of-memory crash.
  • "When is an Adjacency Matrix preferred?" -> Answer: In dense graphs where E \approx V², or when we need to perform constant-time edge exist checks matrix[u][v].

    • Common Mistakes

    Warning: 1. Directed Edge Duality: Accidentally adding directed edges in both directions inside directed graph helpers, creating unintended cycle paths.
    > 2. 1-Based Indexing Crashes: Backing lists by size-V arrays while node inputs utilize 1-based indices (e.g. vertex numbers 1 to V). This will cause an Index Out of Bounds exception. Always subtract 1 or size arrays to V + 1.

    7. Summary

  • Graph: Set of Vertices and connecting Edges G=(V,E).
  • Adjacency Matrix: O(V²) space. Best for dense graphs.
  • Adjacency List: O(V + E) space. Best for sparse graphs.

    • 8. Quiz

    Question 1: What is the maximum number of edges in a simple directed graph with V vertices? Answer: V(V - 1) edges (assuming no self-loops).
    Question 2: What is the time complexity to check if there is an edge between vertices U and V in an Adjacency Matrix? Answer: O(1) time, since we directly query matrix[u][v].
    Question 3: If a graph has V vertices and E edges, what is the space complexity of its Adjacency List representation? Answer: O(V + E) space.
    Question 4: True or False: In a tree, the number of edges is always exactly V - 1. Answer: True. A tree is a connected acyclic undirected graph, which always contains exactly V - 1 edges.
    Question 5: What is the 'degree' of a vertex in an undirected graph? Answer: The total number of edges connected to that vertex. For directed graphs, this is split into "indegree" (incoming edges) and "outdegree" (outgoing edges).