## Introduction

When we hear the word graph, what comes to our mind?

Something like this?

Graphs in data structures aren’t like that, though. Then what are they?To understand graphs in data structures, let us consider a family tree.

In a family tree, we can see different family members and the relations between them.

Graphs in data structures are similar where each member of the family is called a node, and their relationships are called edges.

Thus, to formally define it,

*A graph is a non-linear data structure containing points called nodes and links between them called edges. *

In this article, we’ll learn the basics terminologies of graph __Data Structure__ and its types.

## Basic Terminologies

To begin with, let’s see some basic terms related to graphs in data structures.

Let’s transform the family tree above into a generalised graph.

### Vertex or Node

Each point or element in a graph is known as a vertex or node.

In our example above, each family member is a vertex or node.

### Edge or Arc

The link connecting two nodes is called an edge or an arc.

In the graph above, the relations between the members are the edges or arcs.

### End vertices or endpoints

The two nodes joined by an edge are called the end vertices or endpoints of that edge. For example, for the edge between the grandparents, the endpoints are grandma and grandpa.

### Origin

Notice in the family tree above that the link between our parents and us is shown with a unidirectional array. Such an edge is called a directed edge.

In such edges, the first endpoint (here our parents) is known as the origin.

### Destination

In the same case of a directed edge as discussed for an origin, the node containing our siblings and us is called the directed edge’s destination.

### Adjacency and Neighbours

In the example above, if there is a node for a neighbour of ours, then will they be related to us?

Source: __giphy__

Thus, there won’t be any edge between any of our family members or them, but there is an edge between everyone in the same family (although all the edges have not been shown to keep the diagram simple). So, two nodes with an edge are said to be adjacent, and the nodes are called neighbours.

### Incident

In our graph above, all the edges are pointing to a node. So, a node is the endpoint of every edge. In technical terms, the edge is said to be incident on a vertex.

### Outgoing Edge

We saw what the origin is. So there, the edge is pointing away from the origin and is called an outgoing edge.

### Incoming Edge

From the destination end, the edge is called an incoming edge.

### Parallel Edges or Multiple Edges

In graph theory, parallel edges (also called multiple edges or a multi-edge), are two or more edges that are incident to the same two vertices.

### Self Loop

If a node has an edge such that it is both the source and destination, it is called a self-loop. To understand this better, let us see a picture.

### Degree

The degree is the total number of edges connected to a node.

For example, in the example of a family tree, let us consider just ourselves. We are our parents’ kids, our aunt and uncle’s niece or nephew, our grandparents’ grandchild, and our siblings and cousins’ sister or brother.

.

So here, the degree of the node “You” is 11

### In-degree

To understand this, let us consider our previous example again. There, all the edges are directed towards the “you” node. So, the total number of incoming edges for that node is 11. This number is called the in-degree.

### Out-degree

Considering the previous example again, if we consider the opposite relation, i.e., our family includes grandparents, parents, an aunt, an uncle and cousins. The graph for this would be as follows:

Here, all the edges are outgoing edges, and there are 11 of them. So the out-degree of the “you” node is 11.

### Path

Almost all of us have been to a family occasion where we meet a relative and fail to recognise them.

We then try to figure it out by relating who is related to whom. Suppose we want to figure out we are related to a particular cousin, then we will follow the path shown below:

Mom ➡ Grandma and Grandpa ➡ Uncle ➡ Sister

Thus, we can define a path as alternate nodes and edges, leading us to another node.

### Bridge

If our grandparents didn’t exist in our family tree example, would our aunt, uncle and mom or any subsequent generations exist? Of course not. Similarly, in a graph, the node, which on removing makes the graph disconnected, is called the bridge.

### Tree

Let us first see a picture as follows:

.

A graph like this is known as a cycle graph.

A graph without any such cycle is called a tree. For example,

### Forest

A connected graph with many trees is called a forest.

Now that we know some basics of graph data structures, let us learn about the different types of graphs.