# What Is Multigraph in Data Structure With Example?

//

Heather Bennett

In data structure, a multigraph is a type of graph that allows multiple edges between two vertices. Unlike a simple graph, which only allows one edge between two vertices, a multigraph can have parallel edges. Each edge in a multigraph is associated with a weight or label, allowing for more complex relationships between vertices.

## Example:

Let’s consider an example to understand the concept of a multigraph better.

Suppose we have a multigraph representing a transportation network in a city. The vertices in the graph represent different locations, and the edges represent the roads connecting these locations.

• Location A
• Location B
• Location C

### Edges:

• Road 1: Connects Location A to Location B
• Road 2: Connects Location A to Location C
• Road 3: Connects Location B to Location C
• Road 4: Connects Location A to Location B (parallel edge)

In this example, we can see that there are multiple edges between some pairs of vertices. For instance, there are two parallel edges between Location A and Location B (Road 1 and Road 4). This indicates that there are multiple routes or paths available for traveling from one location to another.

The weight or label associated with each edge in the multigraph can represent various attributes such as distance, travel time, or cost. For example, Road 1 might have a weight of “5 km,” while Road 2 might have a weight of “10 km.”

The presence of multiple edges and the associated weights or labels make multigraphs useful in various applications, including transportation planning, network analysis, and optimization problems.

1. Representation of multiple relationships: Multigraphs allow for the representation of multiple relationships between vertices. This can be beneficial when dealing with complex systems or networks where there are multiple interactions or connections between entities.

2. Efficient modeling: In certain scenarios, using a multigraph can lead to a more efficient and accurate model compared to a simple graph. For example, representing parallel edges in a transportation network can help account for different routes or modes of transportation.