Graphs

Bheekya
Definition
● A Graph is a non-linear data structure consisting of vertices
and edges.
● The vertices are sometimes also referred to as nodes and
the edges are lines or arcs that connect any two nodes in
the graph.
● A Graph is composed of a set of vertices( V ) and a set of
edges( E ). The graph is denoted by G(V, E).
Components of a Graph
● Vertices: Vertices are the fundamental units of the graph.
Sometimes, vertices are also known as vertex or nodes.
Every node/vertex can be labeled or unlabelled.

● Edges: Edges are drawn or used to connect two nodes of

the graph. It can be ordered pair of nodes in a directed
graph. Edges can connect any two nodes in any possible
way. There are no rules. Sometimes, edges are also known
as arcs. Every edge can be labelled/unlabelled.
Types Of Graph
● Null Graph: A graph is known as a null graph if there are no edges in the
graph.
● Trivial Graph: Graph having only a single vertex, it is also the smallest
graph possible.
● Undirected Graph: A graph in which edges do not have any direction. That
is the nodes are unordered pairs in the definition of every edge.
● Directed Graph: A graph in which edge has direction. That is the nodes
are ordered pairs in the definition of every edge.
● Connected Graph: The graph in which from one node we can visit any
other node in the graph is known as a connected graph.
● Disconnected Graph: The graph in which at least one node is not
reachable from a node is known as a disconnected graph.
Types Of Graph
● Regular Graph: The graph in which the degree of every vertex is equal to
K is called K regular graph.
● Complete Graph: The graph in which from each node there is an edge to
each other node.
● Cycle Graph: The graph in which the graph is a cycle in itself, the degree
of each vertex is 2.
● Cyclic Graph: A graph containing at least one cycle is known as a Cyclic
graph.
● Directed Acyclic Graph: A Directed Graph that does not contain any cycle.
● Bipartite Graph: A graph in which vertex can be divided into two sets such
that vertex in each set does not contain any edge between them.
Types Of Graph
Weighted Graph
● A graph in which the edges are
already specified with suitable
weight is known as a weighted
graph.
● Weighted graphs can be further
classified as directed weighted
graphs and undirected weighted
graphs.
Applications of Graphs
● Graph data structures are a powerful tool for representing
and analyzing complex relationships between objects or
entities.
● Graphs are useful in fields such as
○ social network analysis
○ recommendation systems
○ computer networks
Representation of Graphs
● There are two ways to store a graph:
○ Adjacency Matrix
○ Adjacency List
Adjacency Matrix
● Adjacency Matrix is a 2D array of size V
x V where V is the number of vertices in
a graph. Let the 2D array be adj[][], a slot
adj[i][j] = 1 indicates that there is an edge
from vertex i to vertex j. Otherwise 0.
● Adjacency matrix for undirected graph is
always symmetric.
● Adjacency Matrix is also used to
represent weighted graphs. If adj[i][j] =
w, then there is an edge from vertex i to
vertex j with weight w.
Adjacency List
● An Adjacency list is an array consisting of
the address of all the linked lists.
● The first node of the linked list represents
the vertex and the remaining lists
connected to this node represents the
vertices to which this node is connected.
● This representation can also be used to
represent a weighted graph. The linked list
can slightly be changed to even store the
weight of the edge.
● There is an array of pointer which points to
the edges connected to that vertex.
Adjacency Matrix Vs Adjacency List
● When the graph contains a large number of edges then it is good to
store it as a matrix because only some entries in the matrix will be
empty.
● If you have a graph with a lot of edges, then the adjacency matrix
might be better.
● If you have a graph with a lot of vertices, then the adjacency list might
be better.
● If you want to be able to quickly tell if there is an edge between two
vertices, then the adjacency matrix might be better.
Operations Adjacency Matrix Adjacency List

Storage Space O(|V|2) O(|V|+|E|)

Adding a vertex In order to add a new vertex to VxV There are two pointers in adjacency list
matrix the storage must be first points to the front node and the
increases to (|V|+1)2. To achieve this other one points to the rear node.Thus
we need to copy the whole matrix. insertion of a vertex can be done
Therefore the complexity is O(|V|2). directly in O(1) time.

Adding an edge To add an edge say from i to j, Similar to insertion of vertex here also
matrix[i][j] = 1 which requires O(1) two pointers are used pointing to the
time. rear and front of the list. Thus, an edge
can be inserted in O(1)time.
Operations Adjacency Matrix Adjacency List

Removing a In order to remove a vertex from V*V In order to remove a vertex, we need to search
vertex matrix the storage must be decreased to for the vertex which will require O(|V|) time in
|V|2 from (|V|+1)2. To achieve this we worst case, after this we need to traverse the
need to copy the whole matrix. Therefore edges and in worst case it will require O(|E|)
the complexity is O(|V|2). time.Hence, total time complexity is O(|V|+|E|).

Removing an To remove an edge say from i to j, To remove an edge traversing through the edges
edge matrix[i][j] = 0 which requires O(1) time. is required and in worst case we need to traverse
through all the edges.Thus, the time complexity
is O(|E|).

Querying In order to find for an existing edge the In an adjacency list every vertex is associated
content of matrix needs to be checked. with a list of adjacent vertices. For a given graph,
Given two vertices say i and j matrix[i][j] in order to check for an edge we need to check
can be checked in O(1) time.. for vertices adjacent to given vertex. A vertex can
have at most O(|V|) neighbours and in worst can
we would have to check for every adjacent
vertex. Therefore, time complexity is O(|V|) .
Tree
● Tree Data Structure is a hierarchical non-linear data structure in
which a collection of elements known as nodes are connected to
each other via edges such that there exists exactly one path between
any two nodes.
Basic Terminologies In Tree Data Structure:
● Parent Node: The node which is a predecessor of a node is called the parent
node of that node. {B} is the parent node of {D, E}.
● Child Node: The node which is the immediate successor of a node is called
the child node of that node. Examples: {D, E} are the child nodes of {B}.
● Root Node: The topmost node of a tree or the node which does not have any
parent node is called the root node. {A} is the root node of the tree. A
non-empty tree must contain exactly one root node and exactly one path
from the root to all other nodes of the tree.
● Leaf Node or External Node: The nodes which do not have any child nodes
are called leaf nodes. {K, L, M, N, O, P, G} are the leaf nodes of the tree.
● Ancestor of a Node: Any predecessor nodes on the path of the root to that
node are called Ancestors of that node. {A,B} are the ancestor nodes of the
node {E}
Basic Terminologies In Tree Data Structure:
● Descendant: Any successor node on the path from the leaf node to that
node. {E,I} are the descendants of the node {B}.
● Sibling: Children of the same parent node are called siblings. {D,E} are
called siblings.
● Level of a node: The count of edges on the path from the root node to that
node. The root node has level 0.
● Internal node: A node with at least one child is called Internal Node.
● Neighbour of a Node: Parent or child nodes of that node are called
neighbors of that node.
● Subtree: Any node of the tree along with its descendant.
Types of Tree data structures:
Types of Tree data structures:
Binary tree: In a binary tree, each node can have a maximum of two children
linked to it. Some common types of binary trees include full binary trees,
complete binary trees, balanced binary trees, and degenerate or pathological
binary trees.

Ternary Tree: A Ternary Tree is a tree data structure in which each node has at
most three child nodes, usually distinguished as “left”, “mid” and “right”.

N-ary Tree or Generic Tree: Generic trees are a collection of nodes where each
node is a data structure that consists of records and a list of references to its
children(duplicate references are not allowed). Unlike the linked list, each node
stores the address of multiple nodes.
Types of Binary Tree:
● Based on the number of children
○ Full Binary Tree: A Binary Tree is a full binary tree if every node has 0 or 2 children.
■ If a full binary tree has i internal nodes:
● Number of leaves l = i+1
● Total number of nodes n = 2*i+1
■ If a full binary tree has n nodes:
● Number of internal nodes i = (n-1)/2
● Number of leaves l=(n+1)/2
■ If a full binary tree has l leaves:
● Total Number of nodes n=2*l-1
● Number of internal nodes i = l-1
○ Degenerate Binary Tree: A degenerate or pathological tree is a tree having a single child either
left or right.
○ Skewed Binary Trees: A skewed binary tree is a pathological/degenerate tree in which the tree is
either dominated by the left nodes or the right nodes.
Types of Binary Tree:
● On the basis of the completion of levels:
○ Complete Binary Tree:
■ a complete binary tree is a binary tree in which every level of the tree is
completely filled except the last level.
■ In the last level, nodes should be attached starting from the left-most position.
■ A complete binary tree of height h satisfies the following conditions:
● From the root node, the level above last level represents a full binary
tree of height h-1
● One or more nodes in last level may have 0 or 1 children
● If a, b are two nodes in the level above the last level, then a has more
children than b if and only if a is situated left of b
Types of Binary Tree:
● On the basis of the completion of levels:
○ Perfect Binary Tree: A Binary tree is a Perfect Binary Tree in which all the
internal nodes have two children and all leaf nodes are at the same level.
○ Balanced Binary Tree: A binary tree is balanced if the height of the tree is
O(Log n) where n is the number of nodes.
○ Binary Search Tree: is a node-based binary tree data structure that has the
following properties:
■ The left subtree of a node contains only nodes with keys lesser than the
node’s key.
■ The right subtree of a node contains only nodes with keys greater than the
node’s key.
■ The left and right subtree each must also be a binary search tree.
■ AVL, red-black trees are balanced binary search trees
Basic Operations on Graphs

● Insertion of Nodes/Edges in the graph – Insert a node into the graph.

● Deletion of Nodes/Edges in the graph – Delete a node from the graph.
● Searching on Graphs – Search an entity in the graph.
● Traversal of Graphs – Traversing all the nodes in the graph.
Spanning Tree:
● A spanning tree is a subset of Graph G, which has all the vertices
covered with minimum possible number of edges. Hence, a spanning
tree does not have cycles and it cannot be disconnected.
● every connected and undirected Graph G has at least one spanning tree.
● A complete undirected graph can have maximum nn-2 number of
spanning trees, where n is the number of nodes. In the above addressed
example, n is 3, hence 33−2 = 3 spanning trees are possible.
● Spanning Tree: Let G = (V,E) be an undirected connected graph. A sub-graph t =
(V, E’) of G is a spanning tree t of G iff t is a tree
○ BFS Spanning tree
○ DFS Spanning tree
Basic Operation Of Tree Data Structure:
● Create – create a tree in the data structure.
● Insert − Inserts data in a tree.
● Search − Searches specific data in a tree to check whether it is present or not.
● Traversal:
● Preorder Traversal – perform Traveling a tree in a pre-order manner in the data
structure.
● In order Traversal – perform Traveling a tree in an in-order manner.
● Post-order Traversal –perform Traveling a tree in a post-order manner.