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?