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.

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.

Incidence

In an undirected graph the edge <V0, V1> is incident on nodes V0 and V1. In a digraph, the edge <V, V1> 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.