Graph representations (adjacency matrix vs list) in Data Structures Theory - Quick Revision & Key Differences

Recall & Review

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array where each cell at row i and column j indicates if there is an edge between vertex i and vertex j. It uses rows and columns to represent connections.

beginner

What is an adjacency list in graph representation?

An adjacency list represents a graph by storing a list of neighbors for each vertex. Each vertex has a list of vertices it connects to, making it efficient for sparse graphs.

intermediate

Which graph representation uses more memory for large sparse graphs: adjacency matrix or adjacency list?

Adjacency matrix uses more memory for large sparse graphs because it stores information for every possible edge, even if many edges don't exist. Adjacency list only stores existing edges.

intermediate

How does checking if an edge exists differ between adjacency matrix and adjacency list?

In an adjacency matrix, checking if an edge exists is fast and direct by looking up the cell. In an adjacency list, you may need to search through the list of neighbors, which can be slower.

beginner

When is it better to use an adjacency list over an adjacency matrix?

Use an adjacency list when the graph has few edges compared to the number of vertices (sparse graph). It saves memory and is efficient for iterating over neighbors.

Which graph representation uses a 2D array to store edges?

A Adjacency matrix

B Adjacency list

C Edge list

D Incidence matrix

An adjacency matrix uses a 2D array where rows and columns represent vertices and cells indicate edges.

Which representation is more memory efficient for a graph with very few edges?

A Adjacency matrix

B Adjacency list

C Both use the same memory

D None of the above

Adjacency lists store only existing edges, so they use less memory for sparse graphs.

How do you check if an edge exists between two vertices in an adjacency matrix?

A Look up the cell at row i and column j

B Search the list of neighbors for vertex i

C Count the total edges

D Check the degree of vertex j

In an adjacency matrix, the presence of an edge is directly indicated by the value in the cell at row i and column j.

Which graph representation is better for quickly iterating over all neighbors of a vertex?

A Adjacency matrix

B Edge list

C Adjacency list

D None of the above

Adjacency lists store neighbors directly, making iteration over them faster and more efficient.

What is a disadvantage of using an adjacency matrix?

A Does not support weighted edges

B Cannot represent directed graphs

C Edges are hard to find

D Uses a lot of memory for large graphs

Adjacency matrices use memory for every possible edge, which can be large for big graphs, especially if many edges are missing.

Explain the difference between adjacency matrix and adjacency list in graph representation.

Think about how each stores connections and when each is useful.

When would you choose an adjacency list over an adjacency matrix? Give reasons.

Consider the number of edges compared to vertices.