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