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.
8+ registered 