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.
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).
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.
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."