# Graph Terminology in Data Structure

A graph is a non-linear data structure. Mathematically graph can be defined by the pair G=(V, E)

where,
V= finite and non-empty set of vertices
E= set of edges which are the pair of vertices

## Basic Terminology of Graph:

### Undirected Graph:

A graph which has unordered pair of vertices is called Undirected Graph.

### Directed Graph:

It is a graph in which each edge is represented by an ordered pair of vertices. The directed graph is also known as Diagraph.

### Weighted Graph:

A graph is said to be weighted if every edge in the graph is assigned some non-negative value as weight. The weight may be the distance of the edge or the cost to travel along the edge or some other positive values depending on some parameters. A weighted graph is also known as Network.

A node V1 is adjacent to or neighbour of another node V2 if there is an edge from node V1 to node V2.

### Incidence:

In an undirected graph the edge is incident on nodes V0 and V1. In a digraph, the edge is incident from node V0 and it is incident to node V1.

### Path and length of path:

Path is a sequence of vertices and edges in which any two consecutive edges are incident and no vertex is repeated. The total number of edges on a path is called its length.

### Cycle and Hamiltonian Cycle:

A Cycle is a path that starts and ends at the same vertex. It is a path where the last vertex is adjacent to the first. A cycle in which no vertex repeats is said to be Simple. The shortest cycle in the graph defines its girth, while a simple cycle that passes through each vertex is said to be a Hamiltonian Cycle.

### Directed Acyclic Graph (DAG):

A Directed Acyclic Graph is a directed graph that has no cycle. For certain applications, it is convenient to deal with graphs that contain no cycles.