Adjacency Matrix Representation in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array used to represent a graph where each cell at row i and column j indicates if there is an edge from vertex i to vertex j.

beginner

How do you represent no edge between two vertices in an adjacency matrix for an unweighted graph?

You represent no edge by storing 0 in the cell corresponding to those two vertices in the adjacency matrix.

intermediate

In an adjacency matrix for a weighted graph, what value is typically used to represent no edge?

A special value like a very large number (e.g., INT_MAX) is used to represent no edge, depending on the implementation.

beginner

What is the time complexity to check if an edge exists between two vertices using an adjacency matrix?

It is O(1) because you directly access the matrix cell at [i][j].

intermediate

What is a disadvantage of using adjacency matrix for graph representation?

It uses O(V²) space, which can be inefficient for graphs with many vertices but few edges (sparse graphs).

What does a 1 in the adjacency matrix cell [2][3] indicate in an unweighted graph?

A There is an edge from vertex 2 to vertex 3

B There is no edge from vertex 2 to vertex 3

C Vertex 2 and 3 are the same

D The graph is weighted

A 1 means an edge exists from vertex 2 to vertex 3.

What is the size of an adjacency matrix for a graph with 5 vertices?

A 4 x 4

B 5 x 4

C 5 x 5

D Depends on number of edges

The adjacency matrix is always V x V, so 5 x 5 for 5 vertices.

Which operation is fastest with adjacency matrix representation?

A List all neighbors of a vertex

B Remove a vertex

C Add a new vertex

D Check if an edge exists between two vertices

Checking edge existence is O(1) by direct access.

What is the space complexity of adjacency matrix for a graph with V vertices?

A O(V²)

B O(V)

C O(E)

D O(1)

Adjacency matrix uses O(V²) space regardless of edges.

In a weighted graph adjacency matrix, what does a 0 usually mean?

A No edge between vertices

B Edge weight zero

C Edge exists with weight 1

D Graph is unweighted

In weighted graphs, 0 can mean edge weight zero; no edge is often represented by a special value like INT_MAX.

Explain how an adjacency matrix represents edges in a graph.

Think of a table where rows and columns are vertices.

Describe the advantages and disadvantages of using adjacency matrix for graph representation.

Consider speed and memory use.