Mastering Graph Structures

A Graph is a collection of Nodes (Vertices) and the connections between them (Edges). It is the most flexible data structure, used for Social Networks, GPS Maps, and Dependency Injection containers.

1. Adjacency Matrix

A 2D array where matrix[i][j] = 1 means there is a connection. It is O(1) to check if a specific edge exists, but it uses O(N^2) space. It is very wasteful if the graph is "Sparse" (has few connections).

2. Adjacency List

An array of Linked Lists. Each node stores only its direct neighbors. It is Memory Efficient and much faster for traversing all neighbors of a node. This is the standard representation for most enterprise algorithms.

3. Directed vs Undirected

• Undirected: The connection goes both ways. (e.g., Facebook friendship).
• Directed (Digraph): The connection has a direction. (e.g., Twitter followers).

4. Interview Mastery

Q: "Which representation would you use for a Global Flight Network?"

Architect Answer: "I would use an **Adjacency List**. While there are thousands of cities (nodes), each city only has a few dozen direct flights (edges). An adjacency matrix would be 99% empty space (O(V^2)). Using a list allows us to traverse only the existing flight paths efficiently, saving massive amounts of memory and CPU cycles."