A Graph is a set of Vertices (Nodes) connected by Edges. It is the ultimate data structure for representing networks—be it social (Mutual Friends), physical (Maps/GPS), or logical (Internet Routing).

Think of a Social Network (Facebook/LinkedIn):

1. Every person is a Node.
2. A friendship is an Edge connecting two people.
3. Directed Graph: If I follow you on Twitter, but you don't follow me back (One-way).
4. Undirected Graph: We are friends on Facebook (Two-way).
5. Weighted Graph: The distance between our houses in miles.

---

Adjacency Matrix

A 2D array matrix[i][j] where 1 means an edge exists.

• Good for: Dense graphs (many edges).
• Bad for: Memory usage ($O(V^2)$).

Adjacency List (The Interview Choice!)

An array of lists. list[i] contains all neighbors of node i.

• Good for: Sparse graphs (most real-world cases).
• Memory: $O(V + E)$.

---

javascript Standard
/**
 * Graph Representation using Map (Adjacency List)
 */
class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(v) {
    if (!this.adjList.has(v)) this.adjList.set(v, []);
  }

  addEdge(u, v, directed = false) {
    this.addVertex(u);
    this.addVertex(v);
    this.adjList.get(u).push(v);
    if (!directed) {
      this.adjList.get(v).push(u);
    }
  }
}

// Example: 0 connected to 1 and 2
const g = new Graph();
g.addEdge(0, 1);
g.addEdge(0, 2);

---

Fundamental Terminology

• Degree: Number of edges connected to a node.
• Path: A sequence of edges from node A to B.
• Cycle: A path that starts and ends at the same node.
• Connected Graph: You can reach any node from any other node.

Questions

• "When would you prefer an Adjacency Matrix over an Adjacency List?" (Answer: When the graph is nearly complete or you need $O(1)$ edge existence check).
• "How many edges can a simple graph with $V$ vertices have?" (Answer: $V(V-1)/2$). 🛰️