Graph Representation

What is an adjacency list?

An adjacency list shows which vertices each vertex is connected to, typically using lists.

What is an adjacency matrix?

An adjacency matrix is a table that shows 1 if two vertices are connected and 0 if not.

What is an incidence matrix?

An incidence matrix represents which vertices are incident (connected) to which edges.

Why do we use different graph representations?

To make it easier to store, visualize, and perform algorithms on graphs, depending on the situation.

Which graph representation is best for sparse graphs?

The adjacency list, because it stores fewer unused connections.

Which graph representation is best for dense graphs?

The adjacency matrix, because it allows fast checking of whether two vertices are connected.