?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Moderate

Representing a Graph using an Adjacency List and Adjacency Matrix

ALGOR-5SJK0Y

A graph is an abstract data type which represents a set of vertices connected by edges. A graph data structure is a concrete implementation of the structure and functionality of the graph abstract data type. There are two main techniques used for storing the structure of a graph in a computer program: an adjacency list and an adjacency matrix.

An adjacency list is simply a list with entries for each vertex in the graph. The entry for each vertex indicates which other vertices are connected to that vertex by an edge. For example, the following adjacency list represents a small graph with 4 vertices:

Vertex Adjacent Vertices
1 2
2 1, 3, 4
3 2, 4
4 2, 3

An adjacency matrix is a V×V matrix, where V is the number of vertices in the graph. For each entry (i, j) in the matrix, a 1 indicates the presence of an edge between vertex i and vertex j in the graph, while a 0 indicates the absence of an edge.

Which of the following adjacency matrices is equivalent to the adjacency list above? In other words, which adjacency matrix represents the same graph as the adjacency list?

A
V 1 2 3 4
1 1 0 1 1
2 0 0 1 1
3 1 1 0 1
4 1 1 1 0
B
V 1 2 3 4
1 0 1 0 0
2 1 0 1 1
3 0 1 0 1
4 0 1 1 0
C
V 1 2 3 4
1 0 1 1 0
2 1 0 1 1
3 1 1 0 1
4 0 1 1 0
D
V 1 2 3 4
1 0 0 0 0
2 1 0 0 0
3 0 1 0 0
4 0 1 1 0