Flat Preloader Icon



1) Graph
2) Adjacent nodes
3) Degree of anode
4) Path
5) Connected Graph
6) Labelled & Weighted Graph
7) Multi Graph &-Directed Graph
8) Complete Graph
9) Representation of Graph

What Is Graph?

  • Graph is nonlinear data structure
  • Graphs are a fundamental data structure used in computer science and mathematics to represent relationships between different entities. They consist of a set of vertices or nodes, connected by edges or links.
  • These vertices can represent any discrete object or entity, while the edges depict the relationships or connections between them.

e0 = [V0, V1]

e1 = [v1, v2 ]

V = {V0, V1, V2, V3, V4 }

E = {e0, e1, e2, e3, e4}

A Graph Consists of two things

A set V of elements called nodes.

A set E of edges such that each edge e in E is identified with a unique (unordered)
pair [u ,v] of nodes in V, denoted by e = [u,v] we indicate the parts of the graph by writing G=(V,E)

Some Common Types Include

  • Directed and Undirected Graphs: In directed graphs, the edges have a specific direction, while in undirected graphs, the edges have no direction.
  • Weighted and Unweighted Graphs: Weighted graphs assign a weight or cost to each edge, whereas unweighted graphs do not.
  • Cyclic and Acyclic Graphs: Cyclic graphs contain cycles, which are paths that lead back to the starting node, while acyclic graphs do not have any cycles.

Directed & Undirected Graph

Undirected Graphs:
  • In an undirected graph, the edges have no specific direction associated with them.
  • They represent symmetric relationships. For example, if there is an edge between nodes A and B, it implies that there is a symmetric relationship between A and B; you can traverse from A to B and vice versa.
  • Formally, an edge {A, B} in an undirected graph indicates a connection between node A and node B, without any notion of a one-way relationship.
Directed Graphs:
  • In a directed graph (also known as a digraph), each edge has a specific direction associated with it.
  • They represent asymmetric relationships. For example, if there is a directed edge from node A to node B, it implies a one-way relationship or a specific direction from A to B.
  • Formally, an edge (A, B) in a directed graph indicates a directed connection from node A to node B.

Adjacent Nodes

If e = [u,v] then u and v
are called adjacent nodes or neighbors .

Degree Of Node

The degree of node u, written deg(u), is the number of edges containing u
If deg(u)=0, then u is called isolated node


A path of length n From a node u to a node v is defined as a sequence of n+1 nodes

p =(v0, v1, v2,…… vn)
The path is said to be closed if v0 =vn

Simple & Complex Path

The Path is said to be simple if all the nodes are distinct, with the exception that v0 may equal to Vn otherwise it is complex path

Connected Graph

A graph is said to be connected if there is a path between any two of its nodes

Tree Graph

A connected graph T without any cycles is called a tree graph or free tree, or simply a tree

This means in particular, that there is a unique simple path P between any two nodes u and v.

Labelled Graph

A graph is to be labelled if its edges are assigned data.

Weighted Graph

A graph G is said to be weighted if each edge e in G is assigned a non-negative numerical value W(e)
called the weight or length of e

Multiple Edge

Distinct edges e and e’  are called multiple edges if they connect the same end points that is ,

if e = [u,v] and e’ = [u ,v]


An edge is called loop if it has identical end points.

IPv4 – 32 Bits

IP v6- 128 Bits

Multi Graph

Multi Graph is a graph consisting of multiple edges and loops

Directed Graph

A directed graph G also called digraph in same as multigraph except that
each edge e is assigned a direction

e = (u,v)

Complete Graph

A simple graph in which there exists an edge between every pair of vertices is called a complete graph.

It is also known as a universal  graph or clique

  • Adjacency Matrix Representation
  • List Representation
  • Suppose G is a simple graph with m nodes, and suppose the nodes of G have been ordered and are called v1, v2, v3 ………..Vm. Then the adjacency matrix A= (aij) of the graph G is the mxm matrix defined as

    1 – v1 is adjacent to vj
    0 – otherwise

The graph is stored as a linked structure. The adjacency list stores information about only those edges that exists. The adjacency list contains a directory and a set of linked lists.

The directory contains one entry for each node of the graph. Each entry in the directory points to a linked list that represents the nodes that are connected to that node Each node of the linked list has three fields , one is node identifier , second is the link to the next field and the third is an optional weight field which contains the weights of the edges

Class Node {
int vertex;
Node next;

class graph{
private int v-count;
private Adj List arr;

class AdList{
private node stand