Adjacency Matrix
- Represents a graph as a square matrix where entries encode whether pairs of vertices are connected.
- Simple to understand and manipulate for basic graph computations (e.g., vertex degree, edge counts).
- Scales with the square of the vertex count and can be cumbersome for large graphs.
Definition
Section titled “Definition”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.
Explanation
Section titled “Explanation”- Rows and columns correspond to the graph’s vertices. Each matrix element indicates the presence or absence of an edge between the vertex for the row and the vertex for the column.
- In the source example, a value of 1 denotes an edge between the corresponding vertices; a value of 0 denotes no edge.
- Adjacency matrices are simple to understand and easy to manipulate, which facilitates calculations of common graph properties such as the degree of a vertex or the number of edges.
- The matrix size grows proportional to the square of the number of vertices, which can make adjacency matrices large for graphs with many vertices.
- The source states that adjacency matrices do not easily represent certain types of graphs, such as weighted or directed graphs; in those cases, other representations (for example, adjacency lists or edge lists) may be more suitable.
Examples
Section titled “Examples”Simple 4-vertex graph
Section titled “Simple 4-vertex graph”The adjacency matrix for a graph with four vertices labeled A, B, C, and D:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 |
| B | 1 | 0 | 1 | 0 |
| C | 0 | 1 | 0 | 1 |
| D | 1 | 0 | 1 | 0 |
- In this matrix, the value in the second row and third column, 1, indicates that there is an edge between vertices B and C.
Algorithmic and analytic examples
Section titled “Algorithmic and analytic examples”- Finding shortest paths: the Floyd-Warshall algorithm uses the adjacency matrix to compute shortest paths between all pairs of vertices.
- Centrality measures: adjacency matrices can be used to calculate graph centrality measures such as degree centrality or betweenness centrality by determining the number of edges connected to each vertex.
Use cases
Section titled “Use cases”- Graph algorithms and data structures
- Network analysis
- Computer vision
Notes or pitfalls
Section titled “Notes or pitfalls”- Advantages: simple and easy to understand; easy to manipulate for quick calculations of common graph properties.
- Disadvantages:
- Size grows with the square of the number of vertices. For example, a graph with 10 vertices has an adjacency matrix with 100 elements; a graph with 100 vertices has an adjacency matrix with 10,000 elements.
- The source notes that adjacency matrices do not easily represent certain types of graphs, such as weighted or directed graphs; alternative representations like adjacency lists or edge lists may be more suitable.
Related terms
Section titled “Related terms”- Adjacency list
- Edge list
- Floyd-Warshall algorithm
- Degree centrality
- Betweenness centrality
- Graph, vertex, edge