GRAPHS

Introduction to Graphs

Graph is a non linear data structure; A map is a well-known example of a graph. In a map various connections are
made between the cities. The cities are connected via roads, railway lines and aerial network. We can assume that
the graph is the interconnection of cities by roads. Euler used graph theory to solve Seven Bridges of Königsberg
problem. Is there a possible way to traverse every bridge exactly once – Euler Tour

Figure: Section of the river Pregal in Koenigsberg and Euler's graph.

Defining the degree of a vertex to be the number of edges incident to it, Euler showed that there is a walk starting
at any vertex, going through each edge exactly once and terminating at the start vertex iff the degree of each,
vertex is even. A walk which does this is called Eulerian. There is no Eulerian walk for the Koenigsberg bridge
problem as all four vertices are of odd degree.

A graph contains a set of points known as nodes (or vertices) and set of links known as edges (or Arcs) which
connects the vertices.

A graph is defined as Graph is a collection of vertices and arcs which connects vertices in the graph. A graph G is
represented as G = ( V , E ), where V is set of vertices and E is set of edges.

Example: graph G can be defined as G = ( V , E ) Where V = {A,B,C,D,E} and

E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}. This is a graph with 5 vertices and 6 edges.

Graph Terminology

1. Vertex : An individual data element of a graph is called as Vertex. Vertex is also known as node. In
above example graph, A, B, C, D & E are known as vertices.

2. Edge : An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented
as (starting Vertex, ending Vertex).

In above graph, the link between vertices A and B is represented as (A,B).

Edges are three types:

1. Undirected Edge - An undirected edge is a bidirectional edge. If there is an undirected edge between vertices A
and B then edge (A , B) is equal to edge (B , A).

2. Directed Edge - A directed edge is a unidirectional edge. If there is a directed edge between vertices A and B
then edge (A , B) is not equal to edge (B , A).

1
 3. Weighted Edge - A weighted edge is an edge with cost on it.

Types of Graphs

1. Undirected Graph

A graph with only undirected edges is said to be undirected graph.

2. Directed Graph

A graph with only directed edges is said to be directed graph.

3. Complete Graph

A graph in which any V node is adjacent to all other nodes present in the graph is known as a complete graph.
An undirected graph contains the edges that are equal to edges = n(n-1)/2 where n is the number of vertices
present in the graph. The following figure shows a complete graph.

4. Regular Graph

Regular graph is the graph in which nodes are adjacent to each other, i.e., each node is accessible from any other
node.

5. Cycle Graph

A graph having cycle is called cycle graph. In this case the first and last nodes are the same. A closed simple path
is a cycle.

2
6. Acyclic Graph

A graph without cycle is called acyclic graphs.

7. Weighted Graph

A graph is said to be weighted if there are some non negative value assigned to each edges of the graph. The
value is equal to the length between two vertices. Weighted graph is also called a network.

Outgoing Edge

A directed edge is said to be outgoing edge on its orign vertex.

Incoming Edge

A directed edge is said to be incoming edge on its destination vertex.

Degree

Total number of edges connected to a vertex is said to be degree of that vertex.

Indegree

Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

Outdegree

Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Parallel edges or Multiple edges

If there are two undirected edges to have the same end vertices, and for two directed edges to have the same
origin and the same destination. Such edges are called parallel edges or multiple edges.

Self-loop

An edge (undirected or directed) is a self-loop if its two endpoints coincide.

Simple Graph

A graph is said to be simple if there are no parallel and self-loop edges.

3
Adjacent nodes

When there is an edge from one node to another then these nodes are called adjacent nodes.
Incidence

In an undirected graph the edge between v1 and v2 is incident on node v1 and v2.
Walk

A walk is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such
that each edge is incident with the vertices preceding and following it.
Closed walk

A walk which is to begin and end at the same vertex is called close walk. Otherwise it is an open walk.

If e1,e2,e3,and e4 be the edges of pair of vertices (v1,v2),(v2,v4),(v4,v3) and (v3,v1) respectively ,then v1 e1 v2
e2 v4 e3 v3 e4 v1 be its closed walk or circuit.

Path

A open walk in which no vertex appears more than once is called a path.

If e1 and e2 be the two edges between the pair of vertices (v1,v3) and (v1,v2) respectively, then v3 e1 v1 e2 v2 be
its path.
Length of a path

The number of edges in a path is called the length of that path. In the following, the length of the path is 3.

An open walk Graph

4
Degree

In an undirected graph, the number of edges connected to a node is called the degree of that node or the degree of
a node is the number of edges incident on it.

In the above graph, degree of vertex v1 is 1, degree of vertex v2 is 3, degree of v3 and v4 is 2 in a connected
graph.

Indegree

The indegree of a node is the number of edges connecting to that node or in other words edges incident to it.

In the above graph,the indegree of vertices v1, v3 is 2, indegree of vertices v2, v5 is 1 and indegree of v4 is zero.

Outdegree

The outdegree of a node (or vertex) is the number of edges going outside from that node .

Graph Representations

Graph data structure is represented using following representations

1. Adjacency Matrix

2. Adjacency List

3. Adjacency Multilists

1. Adjacency Matrix

In this representation, graph can be represented using a matrix of size total number of vertices by total number of
vertices; means if a graph with 4 vertices can be represented using a matrix of 4X4 size.

In this matrix, rows and columns both represent vertices.

This matrix is filled with either 1 or 0. Here, 1 represents there is an edge from row vertex to column vertex and 0
represents there is no edge from row vertex to column vertex.

Adjacency Matrix : let G = (V, E) with n vertices, n  1. The adjacency matrix of G is a 2-dimensional n  n
matrix, A, A(i, j) = 1 iff (vi, vj) E(G) (vi, vj for a diagraph), A(i, j) = 0 otherwise.

5
example : for undirected graph

For a Directed graph

The adjacency matrix for an undirected graph is symmetric; the adjacency matrix for a digraph need not be
symmetric.

Merits of Adjacency Matrix:

From the adjacency matrix, to determine the connection of vertices is easy

n1

The degree of a vertex is

 adj _ mat[i][ j]
j 0

For a digraph, the row sum is the out_degree, while the column sum is the in_degree
n1
n1
ind (vi)  A[ j, i] outd(vi)   A[i, j]
j 0
j 0

6
 2. Adjacency List

In this representation, every vertex of graph contains list of its adjacent vertices. The n rows of the adjacency
matrix are represented as n chains. The nodes in chain I represent the vertices that are adjacent to vertex i.

It can be represented in two forms. In one form, array is used to store n vertices and chain is used to store its
adjacencies. Example:

So that we can access the adjacency list for any vertex in O(1) time. Adjlist[i] is a pointer to to first node in the
adjacency list for vertex i. Structure is

#define MAX_VERTICES 50
typedef struct node *node_pointer;
typedef struct node {
int vertex;
struct node *link;
};
node_pointer graph[MAX_VERTICES];
int n=0; /* vertices currently in use */

Another type of representation is given below.

example: consider the following directed graph representation implemented using linked list

7
This representation can also be implemented using array

For an undirected graph with n vertices and e edges, linked adjacency list requires an array of size n and 2e chain
nodes. For a directed graph, the number of list nodes is only e. the out degree of any vertex may be determined
by counting the number of nodes in its adjacency list. To find in-degree of vertex v, we have to traverse complete
list.

3. Adjacency Multilists

In the adjacency-list representation of an undirected graph each edge (u, v) is represented by two entries one on
the list for u and the other on tht list for v. As we shall see in some situations it is necessary to be able to determin
ie ~ nd enty for a particular edge and mark that edg as having been examined. This can be accomplished easily
if the adjacency lists are actually maintained as multilists (i.e., lists in which nodes may be shared among several
lists). For each edge there will be exactly one node but this node will be in two lists (i.e. the adjacency lists for
each of the two nodes to which it is incident).

For adjacency multilists, node structure is

typedef struct edge *edge_pointer;

typedef struct edge {
short int marked;
int vertex1, vertex2;
edge_pointer path1, path2;
};
edge_pointer graph[MAX_VERTICES];

8
Lists: vertex 0: N0->N1->N2, vertex 1: N0->N3->N4
vertex 2: N1->N3->N5, vertex 3: N2->N4->N5

Figure: Adjacency multilists for given graph

9
 TREES

Tree: A tree is a finite set of one or more nodes such that:

1. There is specially designated node called “THE ROOT NODE”.
2. The remaining nodes are partitioned n (n>0) disjoint sets T1 , T2,T3,---------Tn , which are
called as SUB TREES of the root.

Tree is a non linear data structure defined as a collection of nodes organized in

hierarchical structure. All nodes to the left side of root node is left sub tree while to the right
side of root node is known as right sub node.

Definitions:

Node: Elements of a tree is called as Node. From the above example the nodes are :A,B,C,D,E,F,G

Root Node: The starting node of a tree is called as Root Node.

 Tree will have only one Root Node.
 From the above example the Root node is: A

Edge: The link or connection between two nodes is called as an Edge.

 if there are n nodes the edges are n-1.
 From the above example the edges are: N = 7 nodes, E = 6 edges.

Parent Node: A node with branches from top to bottom is called as Parent node. From the above example the
parent nodes are: A, B, C.

Child Node: A node with edge from bottom to top or the branches of parent node are called as Child node.
From the above example the Child nodes are: B, C, D, E, F, G.

Siblings: The nodes on the same hierarchical level under the same parent node are called as Siblings. From the
above example the Siblings are: B-C: Siblings, D-E: Siblings, F-G: Siblings.

Leaf: A node without child node is called a Leaf. From the above example the Leaf’s are: D, E, F, G.

Internal Nodes: All nodes other than leaf nodes are called as Internal nodes.
1. Nodes with child node is an internal node.
2. From the above example internal nodes are: A, B, C.

10
Degree of a Node: The number of child nodes represents the degree of a nodes. From the above example:
 Degree of A:2  Degree of D:0
 Degree of E:0  Degree of B:2
 Degree of C:2  Degree of G:0
 Degree of F:0

Level: Every step or hierarchy in a tree is called as Level.

1. Level of a tree starts from 0.
2. Every step of Hierarchy the level will be incremented by 1.
3. Level of tree=2

Height: Longest path from leaf node to that node is called as Height. From the above example the height of (A)
is 2.

Depth: Longest path from root node to that node is called as Depth. From the above example the Depth of (D)
is 2, Depth of (g) is 2, Depth of (B) is 1.

Path: Sequence of node from root to leaf is called as Path. From the above example the Path of (A to D) is: A-
B-D, Path of (A to G) is: A-C-G.

Sub-Tree: Node with child node forms a Sub-tree. From the above example the Sub-trees are:
A, B and C, Sub-tree: B, D and E, Sub-tree: C, F and G, Sub-tree: A, B, C, D, E, F, G.

Ancestor Node: A node that is connected to all lower-level nodes is called as Ancestor node. From the above
example the ancestor nodes are: A, B and C.

Terminal Node: A node with degree (0) zero is called as Terminal node. From the above example the terminal
nodes are: D, E, F, G. It is also called as Leaf node.

Non-Terminal Node: A node without degree (0) zero is called as non-Terminal node. From the above example
the non-terminal nodes are: A, B, C.

The main types of trees in data structure are:

1. Binary Tree
A binary tree is a tree data structure where each node has at most two children. These two
children are usually referred to as the left child and right child. It is widely used in
applications such as binary search trees and heaps.

Example: Consider the tree below. Since each node of this tree has only 2 children, it can be
said that this tree is a Binary Tree.

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

Example: Consider the tree below. Since each node of this tree has only 3 children, it can be
said that this tree is a Ternary Tree.
11
 Examples of Ternary Tree:
• Ternary Search Tree: A ternary search tree is a special trie data structure where the child
nodes of a standard trie are ordered as a binary search tree.
• Ternary Heap: A type of heap where each node can have up to three children, though less
common than binary heaps.

3. N-ary Tree (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.

Every node stores the addresses of its children and the very first node’s address will be stored
in a separate pointer called root.
1. Many children at every node.
2. The number of nodes for each node is not known in advance.
Example:

N-ary Tree

Examples of N-ary Trees:

• B-tree: A self-balancing search tree where nodes can have multiple children, usually
used for indexing large databases.
• B+ Tree: A B+ tree is a variation of the B-tree that only stores data in the leaf nodes,
making range queries more efficient.
• Trie (Prefix Tree): A tree where each node represents a character, and paths from the
root to leaves represent strings. It can have a variable number of children for each
node, making it an N-ary tree.

Memory Representation of Binary Tree:

Binary trees can be represented in multiple ways, each with its own advantages, depending on
the use case. Let's explore the two common methods: linked node representation and array
implementation.
12
Representation of Binary Trees
There are two primary ways to represent binary trees:
1. Linked Node Representation
2. Array Representation

1. Linked Node Representation

A tree node consists of three fields, first field is pointer field is called llink[or] lchild, which holds the address of
left sub tree. The second field is information field, which contains actual value stored in node. The third field is
pointer field is called rlink or rchild, which holds the address of right sub tree. OR
This is the simplest way to represent a binary tree. Each node contains data and pointers to
its left and right children.

Advantages:
• It can easily grow or shrink as needed, so it uses only the memory it needs.
• Adding or removing nodes is straightforward and requires only pointer adjustments.
• Only uses memory for the nodes that exist, making it efficient for sparse trees.

Disadvantages:
• Needs extra memory for pointers.
• Finding a node can take longer because you have to start from the root and follow pointers.

2. Array Representation
A. Convert the binary tree into complete binary tree.
B. Assign the array index from root node in increasing order.
C. Process at each level from left to right direction.
D. Create an array of above size and assign the corresponding tree element to
array location.
Array Representation is another way to represent binary trees, especially useful when the tree
is complete (all levels are fully filled except possibly the last, which is filled from left to right). In this method:
• The tree is stored in an array.

• For any node at index i:

o Left Child: Located at 2 * i + 1

o Right Child: Located at 2 * i + 2

13
• Root Node: Stored at index 0

Advantages:
• Easy to navigate parent and child nodes using index calculations, which is fast
• Easier to implement, especially for complete binary trees.

Disadvantages:
• You have to set a size in advance, which can lead to wasted space.
• If the tree is not complete binary tree then then many slots in the array might be
empty, this will result in wasting memory
• Not as flexible as linked representations for dynamic trees

Tree Traversal Techniques:

Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike
linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical
way to traverse them, trees can be traversed in different ways. In this article, we will discuss
all the tree traversal techniques along with their uses

Tree traversal refers to the process of visiting each node in a tree in a systematic manner.

There are two primary approaches to tree traversal:

1. Depth-First Traversal (DFS)
2. Breadth-First Traversal (BFS)

Each of these approaches has several techniques for visiting the nodes in a specific order.
Let’s explore the common tree traversal techniques:

1. Depth-First Traversal (DFS)

14
Depth-First Traversal explores as deep as possible into the tree before backtracking. DFS can be
implemented using recursion or an explicit stack.

a) Preorder Traversal

In Preorder traversal, the order in which nodes are visited is:

• Root → Left Subtree → Right Subtree

Steps:
1. Visit the root node.
2. Traverse the left subtree.
3. Traverse the right subtree.

Uses of Preorder Traversal

• Preorder traversal is used to create a copy of the tree.
• Preorder traversal is also used to get prefix expressions on an expression tree.

b) Inorder Traversal

In Inorder traversal, the order of node visits is:

• Left Subtree → Root → Right Subtree

Steps:
1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.

Uses of Inorder Traversal

15
• In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order.

• To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed
can be used.

• Inorder traversal can be used to evaluate arithmetic expressions stored in expression trees.

c) Postorder Traversal

In Postorder traversal, the order is:

• Left Subtree → Right Subtree → Root

Steps:
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root node.

Uses of Postorder Traversal

• Postorder traversal is used to delete the tree.
• Postorder traversal is also useful to get the postfix expression of an expression tree.
• Postorder traversal can help in garbage collection algorithms, particularly in systems
where manual memory management is used.

Breadth-First Search (BFS)

It is a traversal technique for trees and graphs that explores nodes level by level, starting from the root node and
moving outward to all its direct children, then to their children, and so on.

16
Binary Search Tree:
A Binary Search Tree (or BST) is a data structure used in computer science for organizing and storing data in a sorted
manner. Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child
containing values less than the parent node and the right child containing values greater than the parent node. This
hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.

Construction of a Binary Search Tree (BST)

To construct a Binary Search Tree, you insert elements one by one, following the BST
property:

• If the new key is less than the current node's key, go to the left child.

• If the new key is greater than the current node's key, go to the right child.

• Repeat until you find a suitable None position and insert the node there.

Example 1:
Construct a BST from the following sequence of numbers:
[50, 30, 20, 40, 70, 60, 80]

Step-by-step Insertion:
1. Insert 50 → becomes the root.
2. Insert 30 → less than 50 → goes to the left of 50.
3. Insert 20 → less than 50, less than 30 → goes to the left of 30.
4. Insert 40 → less than 50, greater than 30 → right of 30.
5. Insert 70 → greater than 50 → right of 50.
6. Insert 60 → greater than 50, less than 70 → left of 70.
7. Insert 80 → greater than 50, greater than 70 → right of 70.

17
 S
EXAMPLE 2:
The following numbers are inserted in BST
31, 16, 45, 24, 7, 19, 29

Algorithm for create

1. Start.
2. read item
3. [loop] while(item!=0) do
a. [create a node] p1= new node
b. [assign] p1->info=item
c. P1->lchild = p1->rchild =NULL
d. [check] if root == NULL then
Root =p1
Else
i. Cur=root
ii. Prev =NULL
18
 iii. [loop] while(cur!=NULL) do
[check] if (p1->info < cur->info) then
Prev = cur
Cur = cur->lchild
Else
Prev = cur
Cur = cur->rchild
Endif
[End while]
iv. [check] if (p1->info < prev->info) then
Prev->lchild = p1
Else
Prev->rchild = p1
[Endif]
[end while]
3.Stop

Algorithm for Preorder

1. Start.
2. [check] if (t !=NULL) then
a. Print t->info
b. Preorder(t->lchild)
c. Preorder(t->rchild)
3. Stop

Algorithm for Inorder

1. Start.
2. [check] if (t !=NULL) then
a. Preorder(t->lchild)
b. Print t->info
c. Inorder(t->rchild)
3. stop

Algorithm for Postorder

1. Start.
2. [check] if (t !=NULL) then
a. Postorder(t->lchild)
b. Postorder(t->rchild)
c. Print t->info
3. stop

19