Graph Terminology in Data Structure

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

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.

Adjacent Node:

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


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.