How is an adjacency matrix implemented in a graph?

An adjacency matrix in a graph is implemented as a two-dimensional array where each cell represents a possible edge.

In more detail, 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. In the adjacency matrix, rows and columns are labelled by graph vertices, and we fill the cell at the intersection of row x and column y with an edge weight if there is an edge from vertex x to vertex y. Edge weight indicates the cost to move from vertex x to vertex y. If there is no edge, we can fill that cell with a null value or infinity depending on the context.

For an undirected graph, the adjacency matrix is symmetric about the diagonal. This is because if there is an edge from vertex x to vertex y, there is also an edge from vertex y to vertex x. For a directed graph, the adjacency matrix need not be symmetric because the edges are directed: an edge from x to y does not imply an edge from y to x.

The size of the matrix is VxV where V is the number of vertices in the graph and the value of entries in the matrix can be either 0 or 1 (in an unweighted graph) or can represent the weights (in a weighted graph). For example, if the graph is unweighted, the entry in the i-th row and j-th column of the adjacency matrix is 1 if there is an edge between vertices i and j, and 0 otherwise.

The adjacency matrix is a good implementation for a graph when we want to quickly check if there is an edge connecting two vertices. However, it is not as efficient in terms of space if the graph is sparse (i.e., has few edges), because it still requires space for V^2 elements, most of which are 0. In such cases, an adjacency list or other graph representations may be more efficient.