Problem Statement
Explain different ways to represent graphs in memory. Compare adjacency matrix and adjacency list.
Explanation
Graphs can be represented in memory using two main methods: adjacency matrix and adjacency list. Each has different space and time trade-offs.
An adjacency matrix is a 2D array of size V by V where V is the number of vertices. The cell at row i and column j contains 1 or true if there is an edge from vertex i to vertex j, and 0 or false otherwise. For weighted graphs, the cell contains the edge weight instead of 1. Space complexity is O of V squared which is inefficient for sparse graphs with few edges. Time complexity to check if an edge exists is O of 1 which is very fast, but adding or removing a vertex takes O of V squared time. It is suitable for dense graphs where the number of edges is close to V squared, when you need to quickly check if an edge exists between any two vertices, and when the graph is small.
An adjacency list uses an array of lists where each index represents a vertex and contains a list of adjacent vertices. For vertex i, the list at index i contains all vertices that are directly connected to i. Space complexity is O of V plus E where E is the number of edges, which is much more efficient for sparse graphs. Time complexity to check if an edge exists is O of degree of v where degree is the number of adjacent vertices, which can be up to V in worst case. Adding a vertex is O of 1 and adding an edge is O of 1. It is suitable for sparse graphs with few edges, when you need to iterate over neighbors of vertices frequently, and when memory is limited.
For undirected graphs, each edge appears twice in the adjacency list, once in each vertex's list. For directed graphs, an edge from u to v appears only in u's list. Weighted graphs can be represented by storing pairs of vertex and weight in the adjacency list.
In practice, adjacency lists are more commonly used because most real-world graphs are sparse. Social networks, web graphs, and road networks typically have far fewer edges than the maximum possible V squared edges. However, adjacency matrices are simpler to implement and can be more efficient for dense graphs or when edge existence checks are very frequent.