What Are the Components of Graph in Data Structure?

//

Heather Bennett

In data structure, a graph is a non-linear data structure that consists of a set of vertices (also known as nodes) and a set of edges that connect these vertices. A graph can be used to represent various real-world scenarios such as social networks, computer networks, transportation networks, and more. Understanding the components of a graph is essential for effectively working with this data structure.

Vertices

The first component of a graph is vertices. Vertices are the fundamental building blocks of a graph and represent the entities or objects in the scenario being modeled.

For example, in a social network graph, each person can be represented as a vertex. In computer networks, each device connected to the network can be represented as a vertex.

Edges

The second component is edges. Edges are the connections between vertices in a graph.

They represent relationships or interactions between the entities represented by the vertices. In our social network example, an edge would indicate that two individuals are friends or connected in some way. In computer networks, edges represent physical or logical connections between devices.

Weight

In some cases, graphs may have weighted edges. The weight associated with an edge represents additional information about the connection between two vertices. For example, in a transportation network graph, the weight could represent the distance between two cities or the cost of traveling between them.

Directed vs Undirected Graphs

A third component to consider when working with graphs is whether it is directed or undirected.

• Undirected Graph: In an undirected graph, edges have no specific direction. The relationship represented by an edge works both ways.

If there is an edge connecting vertex A to vertex B, it implies that there is also an edge connecting vertex B to vertex A.

• Directed Graph: In a directed graph, edges have a specific direction. The relationship represented by an edge is one-way. If there is an edge from vertex A to vertex B, it does not imply that there is an edge from vertex B to vertex A.

Two common ways to represent a graph in computer memory are using an adjacency matrix or an adjacency list.