Smartzworld.com Smartworld.

asia

UNIT – III

TREES AND GRAPHS

Basic Tree Concepts:

A tree is a non-empty set one element of which is designated the root of the tree while the remaining
elements are partitioned into non-empty sets each of which is a sub-tree of the root.

A tree T is a set of nodes storing elements such that the nodes have a parent-child relationship that
satisfies the following

• If T is not empty, T has a special tree called the root that has no parent.

• Each node v of T different than the root has a unique parent node w; each node with parent w is a child
of w.

Tree nodes have many useful properties. The depth of a node is the length of the path (or the number of
edges) from the root to that node. The height of a node is the longest path from that node to its leaves.
The height of a tree is the height of the root. A leaf node has no children -- its only path is up to its parent.

Binary Tree:
In a binary tree, each node can have at most two children. A binary tree is either empty or consists
of a node called the root together with two binary trees called the left subtree and the right
subtree.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Tree Terminology:

Leaf node

A node with no children is called a leaf (or external node). A node which is not a leaf is called an

internal node.

Path

A sequence of nodes n1, n2, . . ., nk, such that ni is the parent of ni + 1 for i = 1, 2,. . ., k - 1. The length

of a path is 1 less than the number of nodes on the path. Thus there is a path of length zero from a

node to itself.

For the tree shown in figure 7.2.1, the path between A and I is A, B, D, I.

Siblings

The children of the same parent are called siblings.

For the tree shown in figure 7.2.1, F and G are the siblings of the parent node C and H and I are the

siblings of the parent node D.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Ancestor and Descendent

If there is a path from node A to node B, then A is called an ancestor of B and

B is called a descendent of A.

Subtree

Any node of a tree, with all of its descendants is a subtree.

Level

The level of the node refers to its distance from the root. The root of the tree has level O, and the

level of any other node in the tree is one more than the level of its parent. For example, in the

binary tree of Figure 7.2.1 node F is at level 2 and node H is at level 3. The maximum number of

nodes at any level is 2n.

Height

The maximum level in a tree determines its height. The height of a node in a tree is the length of a

longest path from the node to a leaf. The term depth is also used to denote height of the tree. The

height of the tree of Figure 7.2.1 is 3.

Depth

The depth of a node is the number of nodes along the path from the root to that node. For
instance, node ‘C’ in figure 7.2.1 has a depth of 1.

Assigning level numbers and Numbering of nodes for a binary tree:

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

The nodes of a binary tree can be numbered in a natural way, level by level, left to right. The nodes

of an complete binary tree can be numbered so that the root is assigned the number 1, a left child

is assigned twice the number assigned its parent, and a right child is assigned one more than twice

the number assigned its parent.

Properties of Binary Trees:

Some of the important properties of a binary tree are as follows:

1. If h = height of a binary tree, then

a. Maximum number of leaves = 2h
b. Maximum number of nodes = 2h + 1 - 1
2. If a binary tree contains m nodes at level l, it contains at most 2m nodes at level l + 1.
3. Since a binary tree can contain at most one node at level 0 (the root), it can contain at most 2 l
node at level l.
4. The total number of edges in a full binary tree with n node is n - 1.

Strictly Binary tree:

If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly

binary tree. Thus the tree of figure 7.2.3(a) is strictly binary. A strictly binary tree with n leaves always

contains 2n - 1 nodes.

Full Binary tree:

A full binary tree of height h has all its leaves at level h. Alternatively; All non leaf nodes of a full binary tree
have two children, and the leaf nodes have no children.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

A full binary tree with height h has 2h + 1 - 1 nodes. A full binary tree of height h is a strictly binary tree all of

whose leaves are at level h.

For example, a full binary tree of height 3 contains 23+1 – 1 = 15 nodes.

Complete Binary tree:

A binary tree with n nodes is said to be complete if it contains all the first n nodes of the above numbering

scheme. Figure 7.2.4 shows examples of complete and incomplete binary trees.

A complete binary tree of height h looks like a full binary tree down to level h-1, and the level h is filled
from left to right.

Representation of Binary Trees:

1. Arrays(especially suited for complete and full binary trees)

2. Pointer-based.

Array-based Implementation:

Linked Representation (Pointer based):

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Binary Tree Traversals:

Tree Traversals
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. Following are the generally used ways for traversing
trees.

Example Tree

Depth First Traversals:

(a) Inorder
(b) Preorder
(c) Postorder
Breadth First or Level Order Traversal
Please see this post for Breadth First Traversal.
Inorder Traversal:
Algorithm Inorder(tree)

1. Traverse the left subtree, i.e., call Inorder(left-subtree)

2. Visit the root.

3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Uses of Inorder
In 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 itraversal s reversed, can be
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
used.
Example: Inorder traversal for the above given figure is 4 2 5 1 3.

Preorder Traversal:
Algorithm Preorder(tree)

1. Visit the root.

2. Traverse the left subtree, i.e., call Preorder(left-subtree)

3. Traverse the right subtree, i.e., call Preorder(right-subtree)

Uses of Preorder
Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix
expression on of an expression tree. Please see http://en.wikipedia.org/wiki/Polish_notation to know why
prefix expressions are useful.
Example: Preorder traversal for the above given figure is 1 2 4 5 3.

Postorder Traversal:
Algorithm Postorder(tree)

1. Traverse the left subtree, i.e., call Postorder(left-subtree)

2. Traverse the right subtree, i.e., call Postorder(right-subtree)

3. Visit the root.

Uses of Postorder
Postorder traversal is used to delete the tree. Please see the question for deletion of tree for details.
Postorder traversal is also useful to get the postfix expression of an expression tree. Please
seehttp://en.wikipedia.org/wiki/Reverse_Polish_notation to for the usage of postfix expression.
Example: Postorder traversal for the above given figure is 4 5 2 3 1.

#include <stdio.h>

#include <stdlib.h>

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct node

int data;

struct node* left;

struct node* right;

};

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

struct node* newNode(int data)

struct node* node = (struct node*)

malloc(sizeof(struct node));
node->data = data;

node->left = NULL;

node->right = NULL;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
return(node);

/* Given a binary tree, print its nodes according to the

"bottom-up" postorder traversal. */

void printPostorder(struct node* node)

if (node == NULL)

return;

// first recur on left subtree

printPostorder(node->left);

// then recur on right subtree

printPostorder(node->right);

// now deal with the node

printf("%d ", node->data);

/* Given a binary tree, print its nodes in inorder*/

void printInorder(struct node* node)

if (node == NULL)

return;

/* first recur on left child */

printInorder(node->left);

/* then print the data of node */

printf("%d ", node->data);

/* now recur on right child */

printInorder(node->right);

/* Given a binary tree, print its nodes in preorder*/

void printPreorder(struct node* node)

{
if (node == NULL)

return;

/* first print data of node */

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
printf("%d ", node->data);

/* then recur on left sutree */

printPreorder(node->left);

/* now recur on right subtree */

printPreorder(node->right);

/* Driver program to test above functions*/

int main()

struct node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

printf("\n Preorder traversal of binary tree is \n");

printPreorder(root);

printf("\n Inorder traversal of binary tree is \n");

printInorder(root);

printf("\n Postorder traversal of binary tree is \n");

printPostorder(root);

getchar();

return 0;

Time Complexity: O(n)

Let us prove it:
Complexity function T(n) — for all problem where tree traversal is involved — can be defined as:
T(n) = T(k) + T(n – k – 1) + c
Where k is the number of nodes on one side of root and n-k-1 on the other side.
Let’s do analysis of boundary conditions
Case 1: Skewed tree (One of the subtrees is empty and other subtree is non-empty )
k is 0 in this case.
T(n) = T(0) + T(n-1) + c
T(n) = 2T(0) + T(n-2) + 2c
T(n) = 3T(0) + T(n-3) + 3c
T(n) = 4T(0) + T(n-4) + 4c
…………………………………………
………………………………………….
T(n) = (n-1)T(0) + T(1) + (n-1)c
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
T(n) = nT(0) + (n)c
Value of T(0) will be some constant say d. (traversing a empty tree will take some constants time)
T(n) = n(c+d)
T(n) = (-)(n) (Theta of n)
Case 2: Both left and right subtrees have equal number of nodes.
T(n) = 2T(|_n/2_|) + c
This recursive function is in the standard form (T(n) = aT(n/b) + (-)(n) ) for master method
If we solve it by master method we get (-)(n)
Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(n).

Creation of Binary Tree from In-Order And Pre (Post) Order Traversals:

Construct Tree from given Inorder and Preorder

traversals
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences.
By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and
elements on right are in right subtree. So we know below structure now.

/ \

/ \

D B E F C

We recursively follow above steps and get the following tree.

/ \

/ \

B C

/ \ /

/ \ /

D E F

Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick
next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

Thanks to Rohini and Tushar for suggesting the code.

/* program to construct tree using inorder and preorder traversals */

#include<stdio.h>

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
#include<stdlib.h>

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct node

char data;

struct node* left;

struct node* right;

};

/* Prototypes for utility functions */

int search(char arr[], int strt, int end, char value);

struct node* newNode(char data);

/* Recursive function to construct binary of size len from

Inorder traversal in[] and Preorder traversal pre[]. Initial values

of inStrt and inEnd should be 0 and len -1. The function doesn't

do any error checking for cases where inorder and preorder

do not form a tree */

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)

static int preIndex = 0;

if(inStrt > inEnd)

return NULL;

/* Pick current node from Preorder traversal using preIndex

and increment preIndex */

struct node *tNode = newNode(pre[preIndex++]);

/* If this node has no children then return */

if(inStrt == inEnd)

return tNode;

/* Else find the index of this node in Inorder traversal */

int inIndex = search(in, inStrt, inEnd, tNode->data);

/* Using index in Inorder traversal, construct left and

right subtress */

tNode->left = buildTree(in, pre, inStrt, inIndex-1);

tNode->right = buildTree(in, pre, inIndex+1, inEnd);

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
return tNode;

/* UTILITY FUNCTIONS */

/* Function to find index of value in arr[start...end]

The function assumes that value is present in in[] */

int search(char arr[], int strt, int end, char value)

int i;

for(i = strt; i <= end; i++)

if(arr[i] == value)

return i;

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

struct node* newNode(char data)

struct node* node = (struct node*)malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return(node);

/* This funtcion is here just to test buildTree() */

void printInorder(struct node* node)

if (node == NULL)

return;

/* first recur on left child */

printInorder(node->left);

/* then print the data of node */

printf("%c ", node->data);

/* now recur on right child */

printInorder(node->right);

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

/* Driver program to test above functions */

int main()

char in[] = {'D', 'B', 'E', 'A', 'F', 'C'};

char pre[] = {'A', 'B', 'D', 'E', 'C', 'F'};

int len = sizeof(in)/sizeof(in[0]);

struct node *root = buildTree(in, pre, 0, len - 1);

/* Let us test the built tree by printing Insorder traversal */

printf("\n Inorder traversal of the constructed tree is \n");

printInorder(root);

getchar();

Time Complexity: O(n^2). Worst case occurs when tree is left skewed. Example Preorder and Inorder
traversals for worst case are {A, B, C, D} and {D, C, B, A}.

Threaded Binary Trees:

Threaded Binary Tree

Inorder traversal of a Binary tree is either be done using recursion or with the use of a auxiliary stack. The
idea of threaded binary trees is to make inorder traversal faster and do it without stack and without
recursion. A binary tree is made threaded by making all right child pointers that would normally be NULL
point to the inorder successor of the node (if it exists).
There are two types of threaded binary trees.
Single Threaded: Where a NULL right pointers is made to point to the inorder successor (if successor
exists)
Double Threaded: Where both left and right NULL pointers are made to point to inorder predecessor
and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and
postorder traversal.
The threads are also useful for fast accessing ancestors of a node.
Following diagram shows an example Single Threaded Binary Tree. The dotted lines represent threads.

C representation of a Threaded Node

Following is C representation of a single threaded node.
struct Node

int data;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
Node *left, *right;

bool rightThread;

Since right pointer is used for two purposes, the boolean variable rightThread is used to indicate whether
right pointer points to right child or inorder successor. Similarly, we can add leftThread for a double threaded
binary tree.
Inorder Taversal using Threads
Following is C code for inorder traversal in a threaded binary tree.
// Utility function to find leftmost node in atree rooted with n

struct Node* leftMost(struct Node *n)

if (n == NULL)

return NULL;

while (n->left != NULL)

n = n->left;

return n;

// C code to do inorder traversal in a threadded binary tree

void inOrder(struct Node *root)

struct Node *cur = leftmost(root);

while (cur != NULL)

printf("%d ", cur->data);

// If this node is a thread node, then go to

// inorder successor

if (cur->rightThread)

cur = cur->right;

else // Else go to the leftmost child in right subtree

cur = leftmost(cur->right);

Following diagram demonstrates inorder order traversal using threads.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Priority Queues

Priority Queue is an extension of queue with following properties.

1) Every item has a priority associated with it.
2) An element with high priority is dequeued before an element with low priority.
3) If two elements have the same priority, they are served according to their order in the queue.
A typical priority queue supports following operations.
insert(item, priority): Inserts an item with given priority.
getHighestPriority(): Returns the highest priority item.
deleteHighestPriority(): Removes the highest priority item.
How to implement priority queue?
Using Array: A simple implementation is to use array of following structure.
struct item {

int item;

int priority;

insert() operation can be implemented by adding an item at end of array in O(1) time.
getHighestPriority() operation can be implemented by linearly searching the highest priority item in
array. This operation takes O(n) time.
deleteHighestPriority() operation can be implemented by first linearly searching an item, then
removing the item by moving all subsequent items one position back.
We can also use Linked List, time complexity of all operations with linked list remains same as
array. The advantage with linked list is deleteHighestPriority() can be more efficient as we don’t
have to move items.
Using Heaps:
Heap is generally preferred for priority queue implementation because heaps provide better
performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be
implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority()
can also be implemented in O(Logn) time.
With Fibonacci heap, insert() and getHighestPriority() can be implemented in O(1) amortized time
and deleteHighestPriority() can be implemented in O(Logn) amortized time.
Applications of Priority Queue:
1) CPU Scheduling
2) Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc
3) All queue applications where priority is involved.

Heap operations

Both the insert and remove operations modify the heap to conform to the shape property first,
by adding or removing from the end of the heap. Then the heap property is restored by
traversing up or down the heap. Both operations take O(log n) time.
Insert
To add an element to a heap we must perform an up-heap operation (also known as bubble-
up, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up), by following this algorithm:

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

1. Add the element to the bottom level of the heap.

2. Compare the added element with its parent; if they are in the correct order, stop.
3. If not, swap the element with its parent and return to the previous step.

The number of operations required is dependent on the number of levels the new element
must rise to satisfy the heap property, thus the insertion operation has a time complexity of
O(log n). However, in 1974, Thomas Porter and Istvan Simon proved that the function for the
average number of levels an inserted node moves up is upper bounded by the constant
1.6067.[5] The average number of operations required for an insertion into a binary heap is
2.6067 since one additional comparison is made that does not result in the inserted node
moving up a level. Thus, on average, binary heap insertion has a constant, O(1), time
complexity. Intuitively, this makes sense since approximately 50% of the elements are leaves
and approximately 75% of the elements are in the bottom two levels, it is likely that the new
element to be inserted will only move a few levels upwards to maintain the heap.

As an example of binary heap insertion, say we have a max-heap

and we want to add the number 15 to the heap. We first place the 15 in the position
marked by the X. However, the heap property is violated since 15 > 8, so we need to
swap the 15 and the 8. So, we have the heap looking as follows after the first swap:

However the heap property is still violated since 15 > 11, so we need to swap again:

which is a valid max-heap. There is no need to check left child after this final step.
Before we placed 15 on X in 1-st step, the max-heap was valid, meaning 11 > 5. If
15 > 11, and 11 > 5, then 15 > 5, because of the transitive relation.
Extract
The procedure for deleting the root from the heap (effectively extracting the
maximum element in a max-heap or the minimum element in a min-heap) and
restoring the properties is called down-heap (also known as bubble-
down, percolate-down, sift-down, trickle down, heapify-down, cascade-
down, boogie-down, and extract-min/max).

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

1. Replace the root of the heap with the last element on the last level.
2. Compare the new root with its children; if they are in the correct order,
stop.
3. If not, swap the element with one of its children and return to the previous
step. (Swap with its smaller child in a min-heap and its larger child in a
max-heap.)

So, if we have the same max-heap as before

We remove the 11 and replace it with the 4.

Now the heap property is violated since 8 is greater than 4. In this case,
swapping the two elements, 4 and 8, is enough to restore the heap
property and we need not swap elements further:

The downward-moving node is swapped with the larger of its children

in a max-heap (in a min-heap it would be swapped with its smaller
child), until it satisfies the heap property in its new position. This
functionality is achieved by the Max-Heapify function as defined below
in pseudocode for an array-backed heap A of length heap_length[A].
Note that "A" is indexed starting at 1, not 0 as is common in many real
programming languages.

Max-Heapify (A, i):

left ← 2i
right ← 2i + 1
largest ← i
if left ≤ heap_length[A] and A[left] > A[largest] then:
largest ← left
if right ≤ heap_length[A] and A[right] > A[largest] then:
largest ← right
if largest ≠ i then:
swap A[i] ↔ A[largest]
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Max-Heapify(A, largest)

For the above algorithm to correctly re-heapify the array, the node at
index i and its two direct children must violate the heap property. If they
do not, the algorithm will fall through with no change to the array. The
down-heap operation (without the preceding swap) can also be used to
modify the value of the root, even when an element is not being
deleted.

In the worst case, the new root has to be swapped with its child on
each level until it reaches the bottom level of the heap, meaning that
the delete operation has a time complexity relative to the height of the
tree, or O(log n).
Heap operations

Insert into max heap

A max heap is a binary tree that satisfies the following properties:

- it is complete
- the data item stored in each node is greater than or equal to
the data items stored in its children
A heap, binary heap, or min heap is a binary tree that satisfies
the following properties:
- it is complete
- the data item stored in each node is less than the data items
stored in its children (known as the heap-order property)
Heaps are typically stored in arrays when they are implemented in
a program. (Note: it’s easier to see the heap properties when
it’s drawn as a tree

As mentioned earlier, there are two basic operations to be

performed:
- Inserting an item into the heap
- Finding and removing the minimum item from the heap
Conceptually, both operations are fairly simply. But as with AVL
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

trees, either operation could cause the heap properties to be

violated.
It’s much easier to fix the problems with a heap!

Building A Heap
Building A Heap To create a heap, we repeatedly insert the new values. Ex Build a heap by inserting the
following values in order:

Deleting from a Heap

_ Only the root node can be removed from a heap.
_ We swap the root value with the value in the last position of the heap and
delete the last node.
_ We then bubble this value down the tree, swapping with the smaller of its
2 children. Note this is also a O(logN) operation.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Basic Graph Concepts: Graph and its representations

Graph is a data structure that consists of following two components:
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is
not same as (v, u) in case of directed graph(di-graph). The pair of form (u, v) indicates that there is
an edge from vertex u to vertex v. The edges may contain weight/value/cost.
Graphs are used to represent many real life applications: Graphs are used to represent networks.
The networks may include paths in a city or telephone network or circuit network. Graphs are also
used in social networks like linkedIn, facebook. For example, in facebook, each person is
represented with a vertex(or node). Each node is a structure and contains information like person
id, name, gender and locale. This can be easily viewed
byhttp://graph.facebook.com/barnwal.aashish where barnwal.aashish is the profile name.
See this for more applications of graph.
Following is an example undirected graph with 5 vertices.

Following two are the most commonly used representations of graph.

1. Adjacency Matrix
2. Adjacency List
There are other representations also like, Incidence Matrix and Incidence List. The choice of the
graph representation is situation specific. It totally depends on the type of operations to be
performed and ease of use.
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.
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.
The adjacency matrix for the above example graph is:

Adjacency Matrix Representation of the above graph

Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time.
Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done
O(1).
Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges),
it consumes the same space. Adding a vertex is O(V^2) time.

Adjacency List:
An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be
array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This
representation can also be used to represent a weighted graph. The weights of edges can be
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

stored in nodes of linked lists. Following is adjacency list representation of the above graph.

Adjacency List Representation of the above Graph

Breadth First Traversal for a Graph

Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree (See
mthod 2 of this post). The only catch here is, unlike trees, graphs may contain cycles, so we may
come to the same node again. To avoid processing a node more than once, we use a boolean
visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0,
we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited
vertices, then 2 will be processed again and it will become a non-terminating process. Breadth
First Traversal of the following graph is 2, 0, 3, 1.

Following is C++ implementation of simple Breadth First Traversal from a given source. The
implementation usesadjacency list representation of graphs. STL‘s list container is used to store
lists of adjacent nodes and queue of nodes needed for BFS traversal.
// Program to print BFS traversal from a given source vertex. BFS(int s)

// traverses vertices reachable from s.

#include<iostream>

#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation

class Graph

int V; // No. of vertices

list<int> *adj; // Pointer to an array containing adjacency lists

public:

Graph(int V); // Constructor

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
void addEdge(int v, int w); // function to add an edge to graph

void BFS(int s); // prints BFS traversal from a given source s

};

Graph::Graph(int V)

this->V = V;

adj = new list<int>[V];

void Graph::addEdge(int v, int w)

adj[v].push_back(w); // Add w to v’s list.

void Graph::BFS(int s)

// Mark all the vertices as not visited

bool *visited = new bool[V];

for(int i = 0; i < V; i++)

visited[i] = false;

// Create a queue for BFS

list<int> queue;

// Mark the current node as visited and enqueue it

visited[s] = true;

queue.push_back(s);

// 'i' will be used to get all adjacent vertices of a vertex

list<int>::iterator i;

while(!queue.empty())

// Dequeue a vertex from queue and print it

s = queue.front();

cout << s << " ";

queue.pop_front();

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
// Get all adjacent vertices of the dequeued vertex s

// If a adjacent has not been visited, then mark it visited

// and enqueue it

for(i = adj[s].begin(); i != adj[s].end(); ++i)

if(!visited[*i])

visited[*i] = true;

queue.push_back(*i);

// Driver program to test methods of graph class

int main()

// Create a graph given in the above diagram

Graph g(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

cout << "Following is Breadth First Traversal (starting from vertex 2) \n";

g.BFS(2);

return 0;

Output:

Following is Breadth First Traversal (starting from vertex 2)

2 0 3 1

Note that the above code traverses only the vertices reachable from a given source vertex. All the
vertices may not be reachable from a given vertex (example Disconnected graph). To print all the
vertices, we can modify the BFS function to do traversal starting from all nodes one by one (Like
the DFS modified version) .
Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

the graph.

Applications of Breadth First Traversal

We have earlier discussed Breadth First Traversal Algorithm for Graphs. We have also
discussed Applications of Depth First Traversal. In this article, applications of Breadth First Search
are discussed.
1) Shortest Path and Minimum Spanning Tree for unweighted graph In unweighted graph, the
shortest path is the path with least number of edges. With Breadth First, we always reach a vertex
from given source using minimum number of edges. Also, in case of unweighted graphs, any
spanning tree is Minimum Spanning Tree and we can use either Depth or Breadth first traversal
for finding a spanning tree.
2) Peer to Peer Networks. In Peer to Peer Networks like BitTorrent, Breadth First Search is used
to find all neighbor nodes.
3) Crawlers in Search Engines: Crawlers build index using Bread First. The idea is to start from
source page and follow all links from source and keep doing same. Depth First Traversal can also
be used for crawlers, but the advantage with Breadth First Traversal is, depth or levels of built tree
can be limited.
4) Social Networking Websites: In social networks, we can find people within a given distance ‘k’
from a person using Breadth First Search till ‘k’ levels.
5) GPS Navigation systems: Breadth First Search is used to find all neighboring locations.
6) Broadcasting in Network: In networks, a broadcasted packet follows Breadth First Search to
reach all nodes.
7) In Garbage Collection: Breadth First Search is used in copying garbage collection
using Cheney’s algorithm. Refer this and for details. Breadth First Search is preferred over Depth
First Search because of better locality of reference:
8) Cycle detection in undirected graph: In undirected graphs, either Breadth First Search or
Depth First Search can be used to detect cycle. In directed graph, only depth first search can be
used.
9) Ford–Fulkerson algorithm In Ford-Fulkerson algorithm, we can either use Breadth First or
Depth First Traversal to find the maximum flow. Breadth First Traversal is preferred as it reduces
worst case time complexity to O(VE2).
10) To test if a graph is Bipartite We can either use Breadth First or Depth First Traversal.
11) Path Finding We can either use Breadth First or Depth First Traversal to find if there is a path
between two vertices.
12) Finding all nodes within one connected component: We can either use Breadth First or
Depth First Traversal to find all nodes reachable from a given node.
Many algorithms like Prim’s Minimum Spanning Tree and Dijkstra’s Single Source Shortest
Path use structure similar to Breadth First Search.
There can be many more applications as Breadth First Search is one of the core algorithm for
Graphs.

Depth First Traversal for a Graph

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only
catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again.
To avoid processing a node more than once, we use a boolean visited array.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0,
we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited
vertices, then 2 will be processed again and it will become a non-terminating process. Depth First
Traversal of the following graph is 2, 0, 1, 3

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

See this post for all applications of Depth First Traversal.

Following is C++ implementation of simple Depth First Traversal. The implementation
uses adjacency list representation of graphs. STL‘s list container is used to store lists of adjacent
nodes.
#include<iostream>

#include <list>

using namespace std;

// Graph class represents a directed graph using adjacency list representation

class Graph

int V; // No. of vertices

list<int> *adj; // Pointer to an array containing adjacency lists

void DFSUtil(int v, bool visited[]); // A function used by DFS

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // function to add an edge to graph

void DFS(int v); // DFS traversal of the vertices reachable from v

};

Graph::Graph(int V)

this->V = V;

adj = new list<int>[V];

void Graph::addEdge(int v, int w)

adj[v].push_back(w); // Add w to v’s list.

void Graph::DFSUtil(int v, bool visited[])

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
{

// Mark the current node as visited and print it

visited[v] = true;

cout << v << " ";

// Recur for all the vertices adjacent to this vertex

list<int>::iterator i;

for(i = adj[v].begin(); i != adj[v].end(); ++i)

if(!visited[*i])

DFSUtil(*i, visited);

// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()

void Graph::DFS(int v)

// Mark all the vertices as not visited

bool *visited = new bool[V];

for(int i = 0; i < V; i++)

visited[i] = false;

// Call the recursive helper function to print DFS traversal

DFSUtil(v, visited);

int main()

// Create a graph given in the above diagram

Graph g(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

cout << "Following is Depth First Traversal (starting from vertex 2) \n";

g.DFS(2);

return 0;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
}

Output:

Following is Depth First Traversal (starting from vertex 2)

2 0 1 3

Note that the above code traverses only the vertices reachable from a given source vertex. All the
vertices may not be reachable from a given vertex (example Disconnected graph). To do complete
DFS traversal of such graphs, we must call DFSUtil() for every vertex. Also, before calling
DFSUtil(), we should check if it is already printed by some other call of DFSUtil(). Following
implementation does the complete graph traversal even if the nodes are unreachable. The
differences from the above code are highlighted in the below code.

#include<iostream>

#include <list>

using namespace std;

class Graph

int V; // No. of vertices

list<int> *adj; // Pointer to an array containing adjacency lists

void DFSUtil(int v, bool visited[]); // A function used by DFS

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // function to add an edge to graph

void DFS(); // prints DFS traversal of the complete graph

};

Graph::Graph(int V)

this->V = V;

adj = new list<int>[V];

void Graph::addEdge(int v, int w)

adj[v].push_back(w); // Add w to v’s list.

void Graph::DFSUtil(int v, bool visited[])

// Mark the current node as visited and print it

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
visited[v] = true;

cout << v << " ";

// Recur for all the vertices adjacent to this vertex

list<int>::iterator i;

for(i = adj[v].begin(); i != adj[v].end(); ++i)

if(!visited[*i])

DFSUtil(*i, visited);

// The function to do DFS traversal. It uses recursive DFSUtil()

void Graph::DFS()

// Mark all the vertices as not visited

bool *visited = new bool[V];

for(int i = 0; i < V; i++)

visited[i] = false;

// Call the recursive helper function to print DFS traversal

// starting from all vertices one by one

for(int i = 0; i < V; i++)

if(visited[i] == false)

DFSUtil(i, visited);

int main()

// Create a graph given in the above diagram

Graph g(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

cout << "Following is Depth First Traversal (starting from vertex 0) \n";

g.DFS();

jntuworldupdates.org Specworld.in