Select Page

Directed Graphs:

Directed graphs, also known as digraphs, are graphs where edges have a direction associated with them. Each edge connects two vertices but has a specific direction indicating a one-way relationship between the vertices. Directed graphs are used to model relationships where the direction of interaction matters, such as dependencies, flows, or hierarchies.

In a directed graph:

  • Each edge is represented by an ordered pair of vertices (u, v), where u is the source vertex and v is the destination vertex.
  • Edges may have different meanings or interpretations depending on their direction.

Sequential Representations of Graphs:

Sequential representations of graphs store graph data sequentially in memory using arrays or lists. These representations are simple and easy to implement but may have limitations in terms of memory usage and efficiency, especially for large graphs.

Adjacency Matrix:

An adjacency matrix is a common sequential representation of graphs using a two-dimensional array. In an adjacency matrix:

  • Rows and columns represent vertices of the graph.
  • Each cell (i, j) in the matrix indicates whether there is an edge from vertex i to vertex j.
  • For an unweighted graph, the cell contains a 1 if an edge exists, and 0 otherwise.
  • For a weighted graph, the cell contains the weight of the edge, or a special value (e.g., infinity) if no edge exists.

Adjacency Matrices:

An adjacency matrix is a square matrix used to represent a graph, where the rows and columns correspond to vertices, and the entries represent edges between vertices. For a directed graph, the matrix may not be symmetric, as edges may have different directions.

Example of an Adjacency Matrix:

Consider the following directed graph with four vertices (labeled from 0 to 3) and edges:


0 -> 1

| / |

v v v

3 <- 2


The corresponding adjacency matrix would be:


| 0 1 2 3


0 | 0 1 0 1

1 | 0 0 1 0

2 | 0 0 0 1

3 | 1 0 0 0


In this matrix:

  • There is an edge from vertex 0 to vertex 1, vertex 0 to vertex 3, and vertex 3 to vertex 2.
  • There is an edge from vertex 1 to vertex 2.
  • There is an edge from vertex 2 to vertex 3.

Each row corresponds to a source vertex, and each column corresponds to a destination vertex. The value in cell (i, j) indicates the existence of an edge from vertex i to vertex j.

Adjacency matrices are efficient for checking the presence of edges and for certain graph operations but may consume more memory, especially for sparse graphs. They are suitable for small to medium-sized graphs with relatively few vertices and edges.