Introduction to Graphs

Graphs are fundamental data structures used to model pairwise relationships between objects. They are widely used in coding interviews and real-world applications like social networks, navigation systems, and recommendation engines.

1. Graph Basics

Components

• Vertices (Nodes): Represent entities (e.g., people, cities).
• Edges (Links): Represent relationships between vertices (e.g., friendships, roads).

Key Concepts

• Cycle: A path that starts and ends at the same vertex (e.g., A → B → C → A).
• Directed vs. Undirected Graphs:
  • Directed: Edges have a direction (e.g., Twitter follow relationships).
  • Undirected: Edges are bidirectional (e.g., Facebook friendships).

2. Graph Representations

A. Matrix (Grid)

• Structure: A 2D array where each cell represents a node.

• Edges: Implicitly defined by movement rules (e.g., up/down/left/right).

• Example:

  grid = [
      [0, 1, 0],
      [0, 0, 1],
      [1, 0, 0]
  ]
  

  • 0: Free space (traversable).
  • 1: Blocked space (non-traversable).

B. Adjacency Matrix

• Structure: A V x V matrix (V = number of vertices).

  • matrix[i][j] = 1 if there’s an edge from vertex i to j.
  • matrix[i][j] = 0 otherwise.

• Example:

     A  B  C
  A [0, 1, 0]
  B [0, 0, 1]
  C [1, 0, 0]
  

  • Use Case: Rare due to O(V²) space complexity.

C. Adjacency List