An adjacency matrix is a square matrix used to represent a directed graph. In an adjacency matrix, each row and column correspond to a node in the graph, and the elements of the matrix indicate whether there is an edge (connection) between nodes. For a directed graph, the matrix may not be symmetric because edges can have a direction.
To construct the adjacency matrix for a directed graph, you place a 1 in the matrix at the position corresponding to an edge from the source node to the target node. If there is no edge, you place a 0. Here's an example of constructing an adjacency matrix for a directed graph:
Let's consider a simple directed graph with four nodes (A, B, C, D) and the following directed edges:
- A -> B
- B -> C
- C -> D
- D -> A
The adjacency matrix for this directed graph would look like this:
A B C D
A 0 1 0 0
B 0 0 1 0
C 0 0 0 1
D 1 0 0 0
In this matrix:
- A directed edge from A to B is represented by a 1 in the (A, B) position.
- A directed edge from B to C is represented by a 1 in the (B, C) position.
- A directed edge from C to D is represented by a 1 in the (C, D) position.
- A directed edge from D to A is represented by a 1 in the (D, A) position.
All other entries are filled with 0 to indicate the absence of edges between the corresponding nodes.