How is a graph represented using an adjacency matrix?

A graph is represented using an adjacency matrix by creating a square matrix 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, the rows and columns are labelled by graph vertices, and we fill the cell at the intersection of row v and column w with an edge that connects vertices v and w.

For an undirected graph, the adjacency matrix is symmetric because if there is an edge from vertex v to vertex w, then there is also an edge from vertex w to vertex v. Therefore, the entries of the matrix are either 0 or 1, where 1 denotes the presence of an edge and 0 denotes the absence of an edge.

For a directed graph (also known as a digraph), the adjacency matrix need not be symmetric because the edges have a direction. In this case, the entry in the row v and column w corresponds to an edge from vertex v to vertex w.

If the graph is a weighted graph, then the entries of the adjacency matrix can represent the weight of the edge, rather than simply whether the edge is present or not. For example, if the weight of the edge from vertex v to vertex w is 2, then the cell at the intersection of row v and column w in the adjacency matrix would contain the number 2.

The adjacency matrix is a useful representation of a graph when we want to quickly determine if there is an edge connecting two vertices. However, it is not a space-efficient representation for sparse graphs, where the number of edges is much less than the number of vertices squared. In such cases, an adjacency list or an edge list can be a more efficient representation.