91Ó°ÊÓ

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. If the graph has n vertices, we will have an nxn adjacency matrix. If there is an edge between vertex i and vertex j, the value of the matrix at the (i, j) and (j, i) positions will be 1, otherwise, it will be 0. An adjacency list representation of a graph is an efficient way to store sparse graphs. Instead of using a matrix, we use a list (or an array) where each entry corresponds to a vertex, and the value stored is a list of vertices that are adjacent to that vertex.

First, we will create an empty adjacency list with as many entries as there are vertices in the graph. Each entry will initially be an empty list. Example: If the adjacency matrix is of size 4x4, the initial adjacency list will look like this: ``` [ [], [], [], [] ] ```

Now, iterate through each entry in the adjacency matrix. If the value at the (i, j) position is 1, it means there is an edge between vertex i and vertex j. Thus, we add vertex j to the list of adjacent vertices for vertex i and vertex i to that of vertex j in the adjacency list. Keep in mind that the index starts from 0. Example: Suppose we have the following adjacency matrix: ``` [ [0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0] ] ``` We follow the steps as described: 1. Create the initial adjacency list representation: ``` [ [], [], [], [] ] ``` 2. Iterate through the adjacency matrix: - (0, 1): 1 found, so add 1 to the list of vertex 0, and 0 to the list of vertex 1: ``` [ [1], [0], [], [] ] ``` - (0, 3): 1 found, so add 3 to the list of vertex 0, and 0 to the list of vertex 3: ``` [ [1, 3], [0], [], [0] ] ``` - (1, 2): 1 found, so add 2 to the list of vertex 1, and 1 to the list of vertex 2: ``` [ [1, 3], [0, 2], [1], [0] ] ``` - (2, 3): 1 found, so add 3 to the list of vertex 2, and 2 to the list of vertex 3: ``` [ [1, 3], [0, 2], [1, 3], [0, 2] ] ``` This is the adjacency list representation of the graph represented by the adjacency matrix.