# How Do You Store a Graph in Data Structure?

//

Larry Thompson

How Do You Store a Graph in Data Structure?

Graphs are widely used to represent relationships between objects or entities. They are used in various fields such as computer science, mathematics, and social sciences. Storing a graph in a data structure is an essential task that allows efficient manipulation and analysis of the graph.

## Introduction to Graphs

A graph is a collection of vertices (also known as nodes) and edges that connect these vertices. Vertices can represent any object or entity, while edges represent the relationships between them. Graphs can be either directed (edges have a specific direction) or undirected (edges have no direction).

An adjacency matrix is one way to store a graph in a data structure. It uses a two-dimensional matrix to represent the connections between vertices. The rows and columns of the matrix correspond to the vertices, and each cell represents whether there is an edge connecting the corresponding vertices.

To illustrate this, let’s consider an undirected graph with four vertices: A, B, C, and D. The adjacency matrix for this graph would look like:

```  A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
```

In this example, there is an edge between vertex A and vertex B, as well as between vertex A and vertex C. The other entries in the matrix indicate whether there is an edge between the corresponding vertices.

• Simplicity: The adjacency matrix provides a simple representation of the graph.
• Efficient Edge Lookup: Checking if two vertices are connected by an edge is straightforward and efficient.

• Space Complexity: The space required to store the adjacency matrix is proportional to the square of the number of vertices. It can be inefficient for large graphs.
• Inefficient for Sparse Graphs: If the graph has relatively fewer edges, most entries in the matrix will be zero, resulting in wasted space.

An adjacency list is another way to store a graph in a data structure. Instead of using a matrix, it uses an array of linked lists or arrays to represent the connections between vertices. Each vertex has a list/array associated with it, which contains its neighboring vertices.

To illustrate this, let’s consider the same undirected graph as before:

```A: B -> C
B: A -> D
C: A -> D
D: B -> C
```

In this representation, each vertex is associated with a list/array that contains its neighboring vertices. For example, vertex A is connected to vertices B and C.

• Space Efficiency: The adjacency list requires less space compared to the adjacency matrix for sparse graphs since it only stores information about existing edges.
• Easier Traversal: Traversing all the neighbors of a vertex is easy and efficient using an adjacency list.