A **graph **is a collection of nodes (vertices) and edges that connect pairs of nodes.

• It is a non-linear data structure.

• It is used to create a pairwise relationship between objects.

## » Vertex:

A **vertex **(also called a node or a point) is a basic unit in a graph. It represents an object in the system that is being modeled.

## » Edge:

An **edge **(also called a link or a line) is a connection between two vertices in a graph. It represents a relationship between the two objects that the vertices represent.

**Note**: A Graph, when viewed as an **Abstract Data Type (ADT)**, is a mathematical and abstract representation that defines the structure and operations associated with graphs. In the context of an ADT, a Graph typically consists of a set of vertices (nodes) and a set of edges connecting pairs of vertices.

**» Formally, a graph is denoted as a pair G(V, E)**.

Where **V **represents the finite set **vertices **and **E **represents the finite set **edges**.

• Therefore, we can say a graph includes non-empty set of vertices V and set of edges E.

**Example****‣ **Suppose, **a Graph G=(V,E),**

where **Vertices**, V={a,b,c,d}**Edges**, E={{a,b},{a,c},{b,c},{c,d}}

## Applications of Graph:

Graphs have a wide range of applications across various domains due to their ability to model relationships and connections between entities.

**Some key applications of graphs include:**

- Social Networks
- Routing and Networking
- Transportation Systems
- Database Management
- Computer Networks
- Game Development

## Directed Graph:

A **directed graph**, or **digraph**, is a graph in which the edges have a direction. This means that each edge points from one vertex to another vertex.

## Undirected Graph:

An** undirected graph**, on the other hand, is a graph in which the edges do not have a direction. This means that each edge connects two vertices, but it does not matter which vertex the edge is pointing from.

## Graph Terminologies:

**Linear data structure:**

A linear data structure is a type of data structure where elements are arranged sequentially, and each element has a unique predecessor and successor, except for the first and last elements.

Examples of Linear Data Structures: Arrays, Linked Lists, Stacks, Queues.

**Non-linear data structure:**

A non-linear data structure is a type of data structure where elements are not arranged in a sequential manner. There is no one-to-one relationship between elements.

Examples of Non-Linear Data Structures: Trees, Graphs.

**Cyclic Graph:**

A cyclic graph, also known as a cyclic or non-acyclic graph, is a graph that contains at least one cycle. In graph theory, a cycle is a path of edges and vertices that starts and ends at the same vertex, forming a closed loop.

**Acyclic Graph:**

An acyclic graph, also known as a non-cyclic or acyclic graph, is a graph that does not contain any cycles. In an acyclic graph, it is not possible to traverse a path of edges and vertices and return to the starting point without retracing any edge.

**Directed Acyclic Graph:**

A directed acyclic graph (DAG) is a specific type of acyclic graph where edges have a direction, and there are no cycles. In a DAG, it is impossible to follow the direction of the edges and revisit a vertex, forming a closed loop.