Limited access

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:

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
Select an assignment template