Graph and types of graph in Data Structure

A graph is an abstract data structure that is basically a collection of a finite set of vertices (also called nodes) and edges that connect them.

A graph is called a non-linear data structure because its vertices and edges are not arranged sequentially. Nodes can be connected in multiple ways, allowing insertion or connection of elements at various positions according to specific rules, rather than following a strict linear order.

Definition

We can define graph G is as an ordered set (V, E), where V(G) represents the set of vertices and E(G) represents the edges that connect these vertices.

In the below figure we have a graph

Vertices V(G) = {A, B, C, D}

Edges E(G) = {(A, B), (B, C), (A, D), (C, D)}

Note: All tree can be a graph but all graph cannot be a tree.

There are two types of graph in data structure

Directed Graph

A directed graph G is a graph where each edge of the graph has a direction assigned to it. This direction shows how to go from one vertex to another vertex. A directed graph is also known as a digraph. An edge of a directed graph can be written as an ordered pair (a, b) of nodes in G.

Lets see below example of directed graph

For an edge (A, B)

• The edge starts from vertex A and terminates at vertex B.
• Here A is known as the origin or starting point of edge e and B is known as the destination or terminal point of edge e.
• A is the predecessor of B and B is the successor of A.
• Vertices A and B are adjacent to each other.

Un-Directed Graph

An undirected graph is a graph where the edges have no direction. This means you can move between two connected vertices in both ways. An edge in an undirected graph is written as a pair of nodes (a,b).

Lets see below example of undirected graph

For an edge (A, B)

• An edge connects two vertices, say A and B.
• In an undirected graph, the edge can be traveled both ways (A to B and B to A).
• There is no fixed origin or destination.
• Vertices A and B are called adjacent vertices because they are directly connected.

Some Basic terminology of graph

• Adjacent Vertices: The adjacent vertices of a node are the nodes that are directly connected to it by an edge. You can reach them in just one step.
• Path: A path is a sequence of connected edges that allows you to move from one vertex to another. There may be more than one path between the same two vertices.
• Degree: The degree of a node is the total number of edges connected to it. In a directed graph, it is the sum of in-degree and out-degree, written as deg(a) = indeg(a) + outdeg(a).
• In-Degree: The in-degree of a node is the number of edges that point towards it. It shows how many vertices are connected to this node.
• Out-Degree: The out-degree of a node is the number of edges that start from it. It shows how many vertices this node is pointing to.