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 these vertices.

A Graph is also known as a non-linear data structure because we can insert data anywhere by following some defined rule anywhere.

**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 G is a graph where edges of the graph has a no direction assigned to it. It means we can go from one vertex to another vertex in any direction. An edge of a undirected graph can be written as an ordered pair (a, b) of nodes in G.

**Lets see below example of undirected graph**

For an edge (a, b)

- The edge starts from vertex A and terminates at vertex A.
- 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.

## Some Basic terminology of graph

**Adjacent Vertices :** Adjacent Vertices of a node ‘a’ is list of all the vertices that are connected by that vertex ‘a’.

**Pat**h : It is way to reach one vertix to another vertix. There may be multiple path between two vertix.

**Degree**: The degree of a node is the sum of in-degree and out-degree of a particular node ‘a’. A degree is written as deg(a).

Therefore, **deg(a) =** indeg(a) + outdeg(a).

**In degree :** The in-degree of a node a, is the number of edges that terminate at a. It is written as indeg(a).

**Out degree :** The out-degree of a node a, is the number of edges that originate at a. It is written as outdeg(a).

[wpusb]