Unit - V DS

Data structures Lecture Notes Unit - V
UNIT – V
Trees and Graphs
5.1 Trees:
5.1.1 Basic tree concepts
 A tree consists of a finite set of elements called nodes, and a finite set of
directed lines, called branches, that connect the nodes
 The number of branches associated with a node is the degree of the node
 When the branch is directed toward the node, it is an indegree branch; when the
branch is directed away from the node, it is an outdegree branch
 The sum of the indegree and outdegree branches is the degree of the ndoe
 A tree consists of a finite set of elements, called nodes, and a finite set of
directed lines, called branches, that connect the nodes
 If the tree is not empty, the first node is called the root. The indegree of the
root is, by definition, zero
 The indegree of the root is, by definition, zero
 With the exception of the root, all of the nodes in a tree must have an indegree
of exactly one; that is they may have only one predecessor
 All nodes in the tree can have zero, one, or more branches leaving them; that I,
they may have an outdegree of zero, one, or more(zero or more successors)
 Fig. is a representation of a tree
Terminology
 In addition to root, many different terms are used to describe the attributes of a
tree
1
Prepared by: T. Sunil Kumar Reddy Assoc. Prof., / G. B. Hima Bindu, Asst. Prof., Dept. of CSE & IT, SVCET,
CTR
 A leaf is any node with an outdegree of zero, that is, a node with no successors
 A node that is not a root or a leaf is known as an internal node because it is
found in the middle portion of a tree
 A node is a parent if it has successor nodes that
 is if it has an outdegree greater than zero
 Conversely, a node with a predecessor is a child
 A child has an indegree of one
 Two or more nodes with the same parent are siblings
 An ancestor is any node in the path from root to the node
 An descendent is any node in the path below the parent node; that is, all nodes
in the paths from a give node to a leaf are descendents of that node
 Fig. shows the usage of these terms
 A path is a sequence of nodes in which each node is adjacent to the next one
 Every node in the tree can be reached by following a unique path starting from
the root
 In fig. the path form the root to the leaf I is designated as AFI
 It includes two distinct branches, AF and FI
 The level of a node is its distance from the root
 Because the root has a zero distance from itself, the root is at level 0
 The children of the root are at level 1, their children at level 2, and soforth
 Note the relationships between levels and siblings and in fig. above
 Siblings are always at the same level but all nodes in a level are no necessarily
siblings
 For ex, at level2 C and D are siblings, as are G, H and I
 However D and G are not siblings because they have different parents
 The height of the tree is the level of the leaf in the longest path from the root +
2
CTR
1
 By definition the height of the empty tree is -1
 Fig. above contains nodes at three levels 0,1, and 2
 Its height is 3
 Because the tree is drawn upside down, some texts refer to the depth of a tree
rather than its height
 The level of a node is its distance from the root. The height of a tree is the
level of the leaf in the longer path from the root plus 1
 A tree may be divided into subtrees
 A subtree is any connected structure below the root
 The first node in a subtree is known as the root of the subtree and is used to
name the subtree
 Subtrees can also be further divides into subtees
 In fig below, BCD is a subtree as are E and FGHI
 Note that by this, a single node is a subtree
 Thus, the subtree B can be divided into two subtrees C and D, and the subtree F
contains the subtrees G, H and I
 The concept of subtrees leads us to a recursive definition of a tree: a tree is a set

of nodes that either:
1. Is empty or
2. Has a designated node, called the root, from which hierarchically descend
zero or more subtrees, which are also trees
User representations
 There are three different user representations of trees are
1. Organization chart format
 It is basically the notation we use to represent trees in our figures
 The term we use for this notation in general tree
 The general tree representation of computers components is shown in fig.
3
CTR
2. Indented list
 You will find this used in bill of materials systems in which a parts list
represents the assembly structure of an item
 In fig. above clearly shows the relationship among the various components of a
computer, but graphical representations are not easily generated from a database
syste,
 The bill – of – materials format was created to show the same information using
a textual parts list format
 In a bill of materials, each assembly component is shown indented below to
assembly
 Some bills of materials even show the level number of each component
 Because a bill of materials shows which components are assembled into each
assembly it is sometimes called a goezinto(goesinto) list
 Table shows the computer bill of materials in an indented parts list format
3. Parenthetical listing
4
CTR
 It is used with algebraic expressions

 When a tree is represented in parenthetical notation, each open parenthesis
indicates the start of a new level; each closing parenthesis completes the current
level and moves up one level in the tree
 Consider the tree & its parenthetical notation is A(B(CD)EF(GHI))
 To convert a general tree to its parenthetical notation, we use the code as in

below algorithm
Algorithm convertoparen(root,output)
Convert a general tree to parenthetical notation
Pre root is a pointer to a tree node
Post output contains parenthetical notation
1. Place root in output
2. If(root is a parent)
1. Place an open parenthesis in the output
2. Converttoparen(root’s first child)
3. Loop(more siblings)
1. Converttoparen(roots next child)
4. End loop
5. Place close parenthesis in the output
3. End if
4. Return
End converttoparen
5.1.2 Binary trees

 A binary tree is a tree in which no node can have more than two subtrees, the
maximum outdegree for a node is two
 In other words, a node can have zero, one or two subtrees
5
CTR
 The subtrees are designated as the left subtree and right subtree
 Fig. shows a binary tree with its two subtrees
 Note that each subtree is itself a binary tree
 To better understand the structure of binary tree, see the fig.
 Fig. above contains eight binary trees; the first of which is a null tree
 A null tree is a tree with no nodes, as shown in fig(a)
 A node in a binary tree can have no more than two subtrees
Properties
 Several properties for binary trees that distinguish them from general trees
Height of binary trees
6
CTR
 The height of binary trees can be mathematically predicted

Maximum height
 Given that we need to store N node in a binary tree, the maximum height Hmax is
Hmax=N
 Ex: given,
Nodes = 3
What is maximum height?
In this ex N is 3
Maximum height = 3
 There are four different trees that can be drawn to satisfy a maximum height = 3
 A tree with maximum height is rare
 It occurs, when all nodes in the entire tree have only one successors shown in
fig(g) and fig(h)
Minimum Height
 The minimum height of the tree, Hmin is determined by the following formula:
Hmin = [log2N]+1
 Ex: Given,
Nodes = 3
What is minimum height?
N=3
The minimum height = 2
Minimum nodes. We can turn the calculation around and determine the
minimum number of nodes in a tree of a specified height
 Given a height of the binary tree, H, the minimum number of the nodes in the
tree are given as
Nmin = H
 Ex: Given a tree of height = 3
Nmin=H
Nmin = 3 nodes
as seen in fig(g) and fig(h)
Maximum Nodes
 The formula for the maximum number of nodes is derived from the fact that
each node can have only two descendents
 The height of the binary tree H, the maximum number of nodes in the tree is
given as
Nmax = 2H - 1
 Ex: H=3
Nmax = 7
7
CTR
Balance
 The distance of a node from the root determines how efficiently it can be
located
 The children of any node in a tree can be accessed by following only one
branch path, the one that leads to the desired node
 The nodes at level 1, which are children of the root, can be accessed by
following only two branches from the root
 It stands to reason, therefore, that the sorter the tree, the easier it is to locate any
desired node in the tree
 The concept leads us to a very important characteristic of a binary tree – its
balance
 To determine whether a tree is balanced, we calculate its balance factor
 The balance factor of a binary tree is the difference in height between its left
and right subtrees
 If we define the height of the left subtree as HL and the height of the right
subtree as HR, the balance factor of the tree, B, is determined by the following:
B=HL - HR
 Using this formula, the balances of the eight trees in fig are a. 0 by definition b.
0, c. 1, d. -1, e. 0, f. 1, g. 2, and h.2
 In a balanced binary tree, the height of its subtree differs by no more than
one(its balance factor is -1, 0, or +1), and its subtrees are also balanced
Complete and Nearly complete binary trees
 A complete tree has the maximum number of entries for its height(see Nmax in
“height of binary trees”)
 The maximum number is reached when the last level is full, see fig.
 A tree is considered nearly complete if it has the minimum height for its
nodes(see formula Hmin) and all nodes in the last level are found on the left
 Complete and nearly complete trees are shown in fig.
8
CTR
5.1.3 Binary tree traversals

 A binary tree traversal requires that each node of the tree be processed once
and only once in a predetermined sequence
 The two general approaches to the traversal sequence are:
a. Depth first b. breadth first
 In the depth first traversal the processing proceeds along a path from the root
through one child to the most distant descendant of that first child before
processing a second child
 In other words, in the depth first traversal, we process the descendants of a child
before going on to the next child
 In a breadth first traversal, the processing proceeds horizontally from the root to
all of its children, then to its children’s children, and so forth until all nodes
have been processed
 In other words, in the breadth first traversal each level is completely processed
before the next level is started
Depth first traversal
 Given a binary tree consists of a root, left subtree, and a right subtree, we can
define six different depth – first traversal sequences
 Computer scientists have assigned three of these sequences standard names in
the literature, the other three are unnamed but are easily derived
 The standard traversals are shown in fig.
 The traditional designation of the traversals uses a designation of node(N) for
the root, left(L) for the left subtree and right(R) for the right subtree
9
CTR
 To demonstrate the different traversal sequences for a binary tree we use fig
Preorder Traversal (NLR)

 In the preorder traversal, the root node is processed first, followed by the left
subtree and then the right subtree
 It draws its name from the latin prefix pre, which means to go before
 Thus, the root goes before the subtrees
 In the preorder traversal, the root is processed first, before its subtrees
 Given the recursive characteristic of trees, it is only natural to implement tree
traversals recursively
 First we process the root, then the left subtree, and then the right subtree
 The left subtree inturn processed recursively as the right subtree
 The code for the preorder traversal is shown in algorithm
Algorithm preorder(root)
Traverse a binary tree in node – left – right sequence
Pre root is the entry node of a tree of subtree
Post each node has been processed in order
10
CTR
1. If(root is not null)

1. Process(root)
2. Preorder(leftsubtree)
3. Preorder(rightsubtree)
2. End if
End preorder
 Fig. above contains a binary tree with each node named
 The processing sequence for a preorder traversal processes this tree as follows
1. We process the root A
2. We process the left subtree first
3. To process the left subtree, we process its root B, then its left subtree and
right subtree in order
4. When B’s left and right subtrees have been processed in order we are then
ready to process A’s right subtree, E
5. To process the subtree E; we first process the root and then the left subtree
and right subtree
6. Because there is no left subtree, we continue immediately wit right subtree
which completes the tree
 Fig. below shows another way to visualize the traversal of the tree
 Imagine that we are walking around the tree, starting on the left of the root and
keeping as close to the nodes as possible
 In the preorder traversal we process the node when we meet it for the first time
 This is shown as a black box on the left of the node
 The path is shown as a line following a route completely around the tree and
back to the root
 Fig. next shows the recursive algorithmic traversal of the tree
11
CTR
Inorder Traversal(LNR):
 The inorder traversal processes the left subtree first, then the root, and finally
the right subtree
 The meaning of the prefix in is that the root is processed in between the
subtrees
 Once again we implement the algorithm recursively, as shown below
Algorithm Inorder(root)
Traverse a binary tree in left – node – right sequence
1. Inorder(leftsubtree)
2. Process(root)
3. Inorder(rightsubtree)
2. End if
End Inorder
 Because the left subtree must be processed first, we trace from the root to the
far left leaf node before processing any node
 After processing the left subtree, C, we process its parent node, B
12
CTR
 We are now ready to process the right subtree, D

 Processing D completes the processing of the root’s left subtree, and we are
now ready to process the root, A, followed by its right subtree
 Because the right subtree, E, has no left child, we can process its root
immediately followed by its rights subtree F
 The complete sequence for inorder processing is shown in fig.
 To walk around the tree in inorder sequence, we follow the same path but
process each node when we meet it for the second time
 The processing route is shown in fig(b)
 In the inorder traversal, the root is processed between its subtrees
Post order traversal(LRN)
 The last of the standard traversal is the postorder traversal
 It processes the root node after (Post) the left and right subtrees have been
processed
 It starts by locating the far – left leaf and processing it
 It then processes its right sibling including its subtrees(if any). Finally it process
the root node
 In the postorder traversal, the root is processed after its subtrees
 The recursive postorder traversal logic is shown in algorithm
Algorithm postorder(root)
Traverse a binary tree in left– right – node sequence
1. Postorder(leftsubtree)
2. Postorder(rightsubtree)
3. Process(root)
13
CTR
2. End if
End postorder
 In the tree walk for a postorder traversal we move the processing block to the
right of the node so that we process it as we meet the node for the third time
 The postorder traversal is shown in fig.
 Note that we took the same path in all three walks; only the time of the
processing changed
Breadth first traversals

 In the breadth first traversal of a binary tree, we process all of the children of a
node before proceeding with the next level
 In other words, given a root at level n, we process all nodes at level n, we
process all nodes at level n before proceeding with nodes at level n+1
 To traverse tree in depth – first order, we used a stack
 To traverse a tree in breadth first order, we use a queue
 The pseudocode for a breadth first traversal of our binary tree is shown in
algorithm
Algorithm breadthfirst(root)
Process tree using breadth first traversal
Pre root is node to be processed
Post tree has been processed
1. Set current node to root
2. Createqueue(bfqueue)
3. Loop(current node not null)
1. Process(current node)
2. If(left subtree not null)
1. Enqueue(bfqueue, leftsubtree)
3. End if
14
CTR
4. If(right subtree not null)

1. Enqueue(bfqueue, rightsubtree)
5. End if
6. If(not emptyqueue(bfqueue))
1. Set currentnode to dequeue(bfqueue)
7. Else
1. Set current node to null
8. End if
4. End loop
5. Destroyqueue(bfqueue)
End breadthfirst
 Like depth first traversals, we can trace the traversal with a walk
 This time, however, the walk proceeds in a horizontal fashion, first across the
root level, the across level 1, then across the level2, and so forth until the entire
tree is traversed
 The breadth first traversal is shown in fig.
5.1.4 Applications of binary trees

Expression trees
 An expression is a sequence of tokens that follow prescribed rules
 A token may be either an operand or operator
 Here we consider in the form
Operand – operator - operand
 Arithmetic operators are +, -, * and /
 An expression tree is a binary tree with the following properties:
1. each leaf is an operand
15
CTR
2. the root and internal nodes are operators

3. subrees are subexpressions, with the root being an operator
 Fig. contains infix expression and its expression tree
 Three different expression formats: infix, postfix, and prefix

 Inorder traversal produces infix expression
 Preorder traversal produces prefix expression
 Postorder traversal produces postfix expression
Infix traversal
 We write algorithm, when we print the infix expression tree, we must add an
opening parenthesis at the beginning of each expression and a closing
parenthesis at the end of each expression
 Because the root of three and each of its subtrees represents a sub expression,
we print the opening when we start tree or a subtree and the closing parenthesis
when we have processed all of its children
 Fig. shows the placement of parenthesis as we walk through the tree using an
inorder traversal
16
CTR
Algorithm infix(tree)
Print the infix expression for an expression tree
Pre tree is a pointer to an expression tree
Post the infix expression as been printed
1. if(tree not empty)
1. if(tree token is an operand)
1. print(tree – token)
2. else
1. print(open parenthesis)
2. infix(tree left subtree)
3. print(tree – token)
4. infix(tree right subtrree)
5. print(close parenthesis)
3. end if
2. end if
end infix
Postfix traversal
 The expression uses the basic post order traversal of an binary tree
 Note that it does not require parentheses
 The pseudo code is shown in algorithm
Algorithm postfix(tree)
Print the postfix expression for an expression tree
17
CTR

Post the postfix expression has been printed
1. postfix(tree left subtree)
2. postfix(tree right subtree)
3. print(tree token)
2. end if
end postfix
Prefix traversal
 The final expression tree traversal is the prefix traversal
 It uses the standard preorder tree traversal
 Again, no parentheses are necessary
 The pseudo code is shown in algorithm
Algorithm prefix(tree)
Print the prefix expression for an expression tree
Post the prefix expression has been printed
1. print(tree token)
2. prefix(tree left subtree)
3. prefix(tree right subtree)
2. end if
end prefix
General tree deletions

 No standard rules for general tree insertions, but we can develop standard
deletion rules
A node may be deleted only if it is a leaf this means a node cannot be
deleted if it has any children. (program should provide error message that the
node cannot be deleted until the children are deleted)
 We need to program such that to delete the children first then the requested
node
Changing a general tree to a binary tree

 It is easy to represent binary trees in programs rather than general trees
 The binary tree format can be adopted by changing the meaning of the left and
right pointers
18
CTR
 In a general tree, we use two relationships

1. Parent to child
2. Sibling to sibling
 Using this two relationships, we can represent any general tree as a binary tree
 Consider fig,
1. Identify the branch from the parent to its first child. These branches from
each parent become left pointers in the binary tree shown in fig(b)
2. Then we connect siblings, starting with the far – left child, using a branch
for each sibling to its right sibling shown in fig(c), are the right pointers in
binary tree
3. Last step in conversion process to remove all unneeded branches from the
parent to its children the resulting in fig(d)
4. Although it is valid tree structure, it does not have a traditional binary tree
format. We therefore redraw in fig(e).
5.1.5 Binary search tree

Basic concepts
19
CTR
 A Binary search tree is a binary tree with the following properties:

1. All items in the left subtree are less than the root
2. All items in the right subtree are greater than or equal to the root
3. Each subtree is itself a binary search tree
 Fig. contains five binary search tree

 a&b are complete and balanced
 d is nearly complete and balanced
 c & e are neither complete nor balanced
 Fig. below contains invalid Binary search tree
20
CTR
Binary search tree operations

a. Traversals
 The binary tree traversal operations are identical to the ones discussed as in
previous
 Our interest not only operation but rather in the results it produces
 Let’s begin the traversing the tree in fig
 If we traverse the tree using a preorder traversal, we get the results shown
below
23 18 12 20 44 35 52
 Although this traversal is valid, it is not very useful
 Let’s try a postorder traversal and see if it is more useful
12 20 18 35 52 44 23
 Inorder traversal produces a sequenced list,
12 18 20 23 35 44 52
b. Searches
 Three searches algorithms:
21
CTR
1. Find the smallest node

2. Find the largest node
3. Find a requested node
1. Find the smallest node
 The binary search tree in above fig.. we note that the node with the smallest
value(12) is the far – left leaf node in the tree
 The find smallest node operation therefore, simply follows the left branches
until we get to a leaf
 Algorithm contains the pseudocode
Algorithm findsmallestBST(root)
This algorithm finds the smallest node in a BST
Pre root is a pointer to a nonempty BST or subtree
Return address of smallest node
1. if(left subtree empty)
1. return(root)
2. end if
3. return findsmallestBST(left subtree)
end findsmallestBST
2. Find the largest node

 The logic to find largest node operation in a Binary search tree is the reverse of
finding the smallest node
 This time we start at the tree root and follow the right branches to the far – right
node in the tree, which by definition must be the target
 The pseudo code is shown
Algorithm findlargestBST(root)
This algorithm finds the largest node in a Binary search tree
Pre root is a pointer to a nonempty Binary search tree or subtree
Return address of largest node returned
1. if(right subtree empty)
22
CTR
1. return(root)
2. end if
3. return findlargestBST(right subtree)
end findlargestBST
3. BST search
 The binary tree search locates a specific node in the tree
 To understand, we recall binary search algorithm, is shown in fig.
 The fig. traces each of the possible search paths from the middle element in the
array
 Starting with 23, the binary search examines either 18 or 44 depending on the
search key
 From 18 it examines either 12 or 20, from 44 it examines either 35 or 52
 As is clear in fig, tracing all possible search paths follows the same paths we
see in a binary search tree
 Now let’s reverse the process

 Find a given node in a binary search tree
 Assume we are looking for node 20
 We begin by comparing the search argument, 20, with the value in the tree root
 Because 20 is less than the root value, 23, and because we know that all values
less than the root lie in its left subtree, we go left
 We now compare the search argument with the value in the subtree, 18
 This time the search argument is greater than the root value, 18
 Because we know that values greater than the tree root must lie in the right
23
CTR
subtree
 We go right and find our desired value
 This logic is shown in algorithm
Algorithm searchBST(root, targetkey)

Search a binary search tree for a given value
Pre root is the root to a binary tree or subtree
targetkey is the key value requested
Return the node address if the value is found
null if the node is not in the tree
1. if(empty tree)
not found
1. return null
2. end if
3. if(targetkey<root)
1. return searchBST(leftsubtree, targetkey)
4. else if(targetkey>root)
1. return searchBST(rightsubtree, targetkey)
5. else
found targetkey
1. return root
6. end if
end searchBST
24
CTR
c. Insertion
 The insert node function adds data to a Binary search tree to insert a data all we
need to do is follow the branches to an empty subtree and then insert the new
node
 Insertion takes place at a leaf like node, a node that has only one subtree
All Binary search tree insertions takes place at a leaf or a leaf like node
 Fig. shows our binary search tree after we have inserted two nodes
 We first added node 19

 To locate its insertion point, we searched the tree through the path 23, 18, and
20 to a null left branch
 After locating the insertion point, we inserted the new node as the left subtree of
20
 We then added 38
 This time we searched the tree through 23, 44 and 35 to a null right subtree and
inserted the new node
 In this case, the insertion takes place at a leaf like node
 Although 35 has a right subtree, its left subtree is null
 We would therefore place the new node, 23, as the left subtree of 35
 We are now ready to develop the interest algorithm
 We can write an elegant algorithm that inserts the data into the tree using
recursion
 If the tree or subtree is empty, we simply insert the data at the root
 If we are not at an empty tree, we determine which branch we need to follow
25
CTR
and call recursively to determine whether we are at a leaf yet
Algorithm addBST(root, newnode)

Insert node containing new data into BST using recursion
Pre root is address of current node in a BST
newnode is address of node containing data
Post newnode inserted into the tree
Return address of potential new tree root
1. if(empty tree)
1. set root to newnode
2. return newnode
2. end if
locate null subtree for insertion
3. if(newnode<root)
1. return addBST(left subtree, newnode)
4. else
1. return addBST(right subtree, newnode)
5. end if
end addBST
d. Deletion
 To delete a node from a binary search tree, we must first locate it
 There are four possible cases when we delete a node:
26
CTR
1. The node to be deleted has no children. In this case, all we need to do is

delete the node
2. The node to be deleted has only a right subtree. We delete the node and
attach the right subtree to the deleted node’s parent
3. The node to be deleted has only a left subtree. We delete the node and attach
the left subtree to the deleted node’s parent
4. The node to be deleted has two subtrees. It is possible to delete a node from
the middle of a tree, but the result tends to create very unbalanced trees
 Rather than simply delete the node, therefore, we try to maintain the existing
structure as much as possible by finding data to take the place of the deleted
data
 This can be done in one of two ways:
1. We can find the largest node in the deleted node’s left subtree and move its
data to replace the deleted node’s data or
2. We can find the smallest node on the deleted node’s right subtree and move
its data to replace the deleted node’s
 Regardless of each logic we use, we will be moving data from a leaf or a leaf
like node that can then be deleted
 The pseudo code for the Binary search tree delete is shown in algorithm
Algorithm deleteBST(root, dltkey)

This algorithm deletes a node from a binary search tree
Pre root is reference to node to be deleted
dltkey is key of node to be deleted
Post node deleted
if dltkey not found, root unchanged
Return true if node deleted, false if not found
1. if(empty tree)
1. return false
2. end if
3. if(dltkey<root)
1. return deleteBST(left subtree, dltkey)
4. else if(dltkey>root)
1. return deleteBST(right subtree, dltkey)
5. else
delete node found - - test for leaf node
1. if(no left subtree)
1. make right subtree the root
2. return true
27
CTR
2. else if(no right subtree)

1. make left subtree the root
2. return true
3. else
node to be deleted not a leaf. Find largest node on left subtree
1. save root in deletenode
2. set largest to largestBST(leftsubtree)
3. move data in largest to deletenode
4. return deleteBST(left subtree of deletenode, key of largest)
4. end if
6. end if
end deleteBST
5.1.6 Spanning Tree

Network: A Network is a graph whose lines are weighted spanning tree
28
CTR
 We can derive one or more spanning tree from a connected network

 A spanning tree is a tree that contains all the vertices in the graph
 One interesting algorithm the minimum spanning tree of a network such that the
sum of its weights is guaranteed to be minimal
 If the weights in the network are unique, there is only one minimum spanning
tree
 If there are duplicate weights, there are may be one or more minimum spanning
trees
 There are many applications for minimum spanning trees, all with the
requirement to minimize some aspect of the graph
 For ex, given a network of computers, we can create a tree that connects all of
the computers
 The minimum spanning tree gives us the shortest length of cable that can be
used to connect all computers ensuring that there is a path between any two
computers
 A spanning tree contains all of the vertices in a graph. A minimum spanning
tree is a spanning tree in which total weight of the lines is guaranteed to be the
minimum of all possible trees in the graph
 To create a minimum spanning tree in a strongly connected network that is, in a
29
CTR
network in which there is a path between any two vertices – the edges for the
minimum spanning tree are chosen so that the following properties exist:
1. Every vertex is included
2. The total edge weight of the spanning tree is the minimum possible that
includes a path between any two vertices
Minimum spanning tree example is in Fig.
Data Structure:
graph head
count
first
end graphhead
graph vertex
next vertex
30
CTR
data
indegree
outdegree
intree
first edge
end graphvertex
graphedge
destination
weight
next edge
intree
end graphedge
 Minimum spanning tree pseudocode
Algorithm spanningtree(graph)
Determine the minimum spanning tree of a network
Pre graph contains a network
Post spanning tree determined
1. if(empty graph)
1. return
2. end if
3. loop(through all vertices)
set intree flags false
1. set vertex intree flag to false
2. loop(through all edges)
1. set edge intree flag to false
2. get next edge
3. end loop
4. get next vertex
4. end loop
now derive spanning tree
5. set first vertex to intree
6. set tree to complete to false
7. loop(not treecomplete)
1. set tree complete to tree
2. set minedge to maximum integer
3. set minedgeloc to null
walk through graph checking vertices in tree
1. if(vertex intree AND vertex outdegree > 0)
31
CTR
1. loop(through all edges)

1. if(destination not in tree)
Set destination intree flag to false
1. set treecomplete to false
2. if(edgeweight<minedge)
1. set minedge to edge weight
2. set minedgeloc to edge
3. end if
2. end if
3. get next edge
2. end loop
2. end if
3. get next vertex
5. end loop
6. if(minedgeloc not null)
found edge to inset into tree
1. set minedgeloc intree flag to true
2. set destination intree flag to true
7. end if
8. end loop
end spanning tree
5.2.Graphs
 In the graph each node may have multiple predecessors as well as multiple
successors
 Graphs are very useful structures
 They can be used to solve complex routing problems, such as designing an
routing airlines among the airports they serve
5.2.1 Introduction
 A graph is a collection of nodes, called vertices, and a collection of segments,
called lines, connecting pairs of vertices
 In other words, a graph consists of two sets, a set of vertices and a set of lines
 Graphs may be either directed or undirected
 A directed graph or digraph for short, is a graph in each line has a
direction(arrow head) to its successor
 The lines in a directed graph are known as arcs
 An undirected graph is a graph in which there is no direction on any of the
lines, which are known as edges
 Fig contains an example of both a directed graph (a) and an undirected graph
32
CTR
(b)
 A path is a sequence of vertices in which each vertex is adjacent to the next one
 In fig. {A, B, C, E} is one path and {A, B, E, F} is another
 Note that is both directed(you may travel in indicated direction) and undirected
graph(you may travel in either direction) have paths
 Two vertices in a graph are said to be adjacent vertices (or neighbors) if there is
a path length 1 connecting them
 In fig(a) B is adjacent to A, whereas E is not adjacent to D; on the other hand, D
is adjacent to E
 In fig(b), E and D are adjacent, but D and F are not
 A cycle is a path consisting of atleast three vertices that starts and ends with the
same vertex
 In fig(b) B, C, D, E, B is a cycle
 The same vertices in fig(a) is not a cycle
 A loop is a special case of a cycle in which a single arc begins and ends with
the same vertex
 In a loop the end points of the line are the same
33
CTR
 Two vertices are said to be connected if there is a path between them

 A graph is said to be connected if, ignoring direction, there is a path from any
vertex to any other vertex
 A directed graph is strongly connected if there is a path from each vertex to
every other vertex in the digraph
 A digraph is weakly connected if atleast two vertices are not connected
 A graph shows is a disjoint graph if it is not connected
 Fig. shows
 The degree of a vertex is the number of lines incident to it

 In fig(a) degree of vertex B=3 E=4
 The outdegree of a vertex in a digraph is the number of arcs leaving the vertex;
 The indegree is the number of arcs entering the vertex
 In fig(a) the indegree of vertex B is 1 and its outdegree is 2;
 In fig(b) the indegree of vertex E is 3 and its outdegree is 1
 A tree is a graph in which each vertex has only one predecessor; however a
graph is not a tree
5.2.2 Operations
34
CTR
 Six primitive graph operations that provide the basic modules needed to
maintain a graph
- Insert a vertex
- Delete a vertex
- Add an edge
- Delete an edge
- Find a vertex
- Traverse a graph
Insert a vertex
 It adds a new vertex to a graph
 When it is inserted, it is disjoint; that is, it is not connected to any other vertices
in the list
 Inserting a vertex is just the first step in the insertion process
 After insertion, it must be connected
 Fig. shows a graph before and after a new vertex is added
Delete a vertex
 Delete vertex removes a vertex from the graph
 When a vertex is deleted, all connecting edges are also removed
 Fig shows deleting a vertex
35
CTR
Add edge
 Add edge connects a vertex to a destination vertex
 If a vertex requires multiple edges, add an edge must be called once for each
adjacent vertex
 To add an edge, two vertices must be specified
 If the graph is a digraph, one of the vertices must be specified as the source and
one as the destination
 Fig shows an examples of adding an edge {A, E}, to the graph
Delete Edge
 Delete edge removes one edge from a graph
 Fig. shows an example that deletes the edge {A, E} from the graph
Find vertex
 Find vertex traverses a graph, looking for a specified vertex
36
CTR
 If the vertex is found its data are returned

 If it is not found, an error is indicated
 In fig find vertex traverses the graph, looking for vertex C
5.2.3 Traverse graph

 Atleast one application that requires that all vertices in a given graph be visited;
that is, there is atleast one application that the graph be traversed
 Because a vertex in graph can have multiple parents, the traversal of a graph
presents some problems not found in traversal of linear list and trees
 We must ensure that the vertex is visited only once
 The traditional solution is to include visited flag at each vertex
 Initially before traversal we set the visited flag in each vertex to off
 Then, as we traverse the graph, we set the visited flag to on to indicate that the
data have been processed
 Two standard graph traversals are:
b. Depth first and
c. Breadth first
a. Depth first traversal
 In the depth first traversal, we process all a vertex’s descendents before we
move to an adjacent vertex
 This is easy when the graph is a tree
 In fig. we show the tree preorder traversal processing sequence
37
CTR
 The depth first traversal of a graph starts by processing the first vertex of the
graph
 After processing the first vertex, we select any vertex adjacent to the first vertex
and process it
 We process each vertex, we select an adjacent vertex until we reach a vertex
with no adjacent entries
 The logic requires a stack (recursion) to complete the traversal
 The traversal processes adjacent vertices in descending, or last – in – first out
(LIFO) order
 Trace a DFT through a graph in fig.
 The number in the box next to a vertex indicates the processing order
 The stacks below the graph show the stack contents as we work our way down
the graph and then as we back out
1. We begin by pushing the first vertex A, into the stack
2. We then loop, pop the stack, and, after processing the vertex, push all of the
adjacent vertices into the stack, process it and then push G and into the
stack, giving the stack contents for step 3 as shown in fig (B) – HG
3. When the stack is empty the traversal is complete
38
CTR
Breadth first traversal

 In the BFT of a graph, we process all adjacent vertices of a vertex before going
to the next level
 Looking at the tree in fig, we see that its BFT starts at level 0 and then process
all the vertices in level 1 before going to process the vertices in level 2
 The BFT of a graph follows the same concept

 We begin at starting vertex (A); after processing it we process all of its adjacent
vertices (BCD)
 After we process all of the first vertex’s adjacent vertices, we pick its first
adjacent vertex(B) and process all of its vertices, and so forth until we are
finished
39
CTR
 We show that the BFT uses a queue of its adjacent vertices in the queue
 Then select the next vertex to be processed, we delete a vertex from the queue
and process it
 Lets trace the graph in fig.
Breadth first traversal of graph

1. We begin by enqueing vertex A in the queue
2. We then loop, dequeing the queue and processing the vertex from the front of
the queue. After processing the vertex, we places of its adjacent vertices into the
queue. Thus at step 2 in fig (b), we dequeue vertex X, process it, and then place
vertices G and H in the queue. We are then ready for step 3, in which we
process vertex G
3. when the queue is empty, the traversal is complete
In the BFT, all adjacent vertices are processed before processing the descendents
of a vertex
5.2.4 Graph storage structures
 To represent a graph, we need to store two sets
 First set represents the vertices of the graph, and the second set represents the
edges or arcs
 Two most common structures used to store these sets are arrays and linked lists
a. Adjacency matrix
 The adjacency matrix uses a vector(1-D array) for the vertices and a matrix (2 –
D array) to store the edges (See fig)
40
CTR
 If vertices are adjacent – that is, if there is an edge between them – the matrix
intersect has a value of 1; if there is no edge between them, the intersect is set to
0.
 If the graph is directed, the intersection in the adjacency matrix indicates the
direction
 For ex, if fig(b) there is an arc from source vertex B to destination vertex C
 In the matrix, this is arc is seen as 1, in the intersection from B (on the left) to C
(on the top)
 Because there is no arc from C to B
 The intersection from C to B is 0
 In fig(a) the edge from B to C is bidirectional that is you can traverse in either
direction
 So, from B to C is 1 as well as C to B is also 1
 The matrix reflects the fact that you can use the edge to go either way.
In adjacency matrix representation, we use a vector to store the vertices and a

matrix to store the edges
41
CTR
Limitation of adjacency matrix

 I need to know the size of the graph before the program starts
 Only one edge can be stored between any two vertices. Some network
structures require multiple lines between vertices
b. Adjacency list
 The adjacency list uses a two – D ragged array to store the edges
 An adjacency list is shown in fig.
 The vertex list is a singly linked list of the vertices in the list
 It could be implemented using a doubly or circularly linked lists
 The pointer at the left of the list links the vertex entries
 The pointer at the left of the list links the vertex entries
 The pointer at the right in the vertex is a head pointer to a linked list of edges
from the vertex
 Thus, in the nondirected graph on the left in fig, there is a path from vertex B to
vertex A, C, and E
 To find these edges in the adjacency list, we start at B’s vertex list entry and
traverse the linked list to A, then to C, and finally to E
In the adjacency list, we use a linked list to store the vertices an a 2 – D linked list
to store the arcs
5.2.5 Graph Algorithms

a. Create Graph
 Create graph initializes the metadata elements for a graph head structure
 The code is shown in algorithm
Algorithm creategraph
Initializes the metadata elements of a graph structure
Pre graph is a reference to metadata structure
42
CTR
Post metadata elements have been initialized

1. set count to 0
2. set first to null
3. return graph head
end creategraph
b. Insert Vertex
 Insert vertex adds a disjoint that is an unconnected – vertex to the graph
 The arcs associated with the vertex must be inserted separately
Algorithm insertvertex(graph, dataIn)
Allocates memory for a new vertex and copies data to it
Pre graph is a reference to graph head structure
dataIn contains data to be inserted into vertex
Post new vertex allocated and data copied
1. allocate memory for new vertex
2. store dataIn in new vertex
3. initialize metadata elements in newnode
4. increment graph count
now find insertion point
5. if(empty graph)
1. set graph first to newnode
6. else
1. search for insertion point
2. if(inserting before first vertex)
1. set graph first to new vertex
3. else
1. insert new vertex in sequence
4. end if
7. end if
end insertvertex
c. Delete Vertex
 To delete a vertex first we need to find it
 Once we have found it, we need to make sure that is disjoint; that is, we need to
ensure that there are no arcs leaving or entering the vertex
 If there are, we reject the deletion
Algorithm deletevertex(graph, key)
Deletes an existing vertex only if its degree is 0
Pre graph is a reference pointer to graph head
key is the key of the vertex to be deleted
43
CTR
Post vertex deleted(if degree zero)

Return +1 if successful
-1 if degree not zero
-2 if key not found
1. if(empty graph)
1. return -2
2. end if
locate vertex to be deleted
3. search for vertex to be deleted
4. if(not found)
1. return -2
5. end if
found vertex to be deleted. Test degree
6. if(vertex indegree>0 or outdegree>0)
1. return -1
7. end if
okay to delete vertex
8. delete vertex
9. decrement graph count
10.return 1
end deletevertex
d. Insert arc
 Insert arc requires two points in the graph: the source vertex (fromptr) and the
destination vertex (toptr)
 Each is identified by its key value rather than by its physical address
Algorithm insertArc(graph, fromkey, tokey)
Adds an arc between two vertices
Pre graph is reference to graph head structure
fromkey is the key of the originating vertex
tokey is the key of the destination vertex
Post arc added to adjacency list
-2 if fromkey not found
-3 if tokey not found
1. allocate memory for new arc
2. search and set from vertex
3. if(from vertex not found)
1. return -2
44
CTR
4. end if
5. search and set to vertex
6. if(tovertex not found)
1. return -3
7. end if
8. increment from vertex outdegree
9. increment tovertex indegree
10.set destination to tovertex
11.if(fromvertex arc list empty)
1. set fromvertex firstarc to newarc
2. set newarc nextarc to null
3. return 1
12.end if
13.find insertion point in arc list
14.if(insert at beginning of arc list)
1. set from vertex first arc to newarc
15.else
1. insert in arclist(adjacency list)
16.end if
17.return 1
end insertarc
e. Delete Arc
 It removes one arc from the adjacency list
 To identify an arc, we need to vertices
 The vertices are identified by their key
 The algorithm therefore searches the vertex list for the start vertex and then
searches its adjacency list for the destination vertex
 After locating and deleting the arc, the degree in the form and to vertices is
adjusted and the memory recycles
Algorithm deleteArc(graph, fromkey, tokey)
Delete arc between two vertices
Pre graph is reference to a graph head structure
fromkey is the key of the originating vertex
tokey is the key of the destination vertex
Post vertex deleted
-2 if fromkey not found
-3 if key not found
45
CTR
1. if(empty graph)
1. return -2
2. end if
3. search and set fromvertex tovertex with key equal to fromkey
4. if(fromvertex not found)
1. return -2
5. end if
6. if(fromvertex arc list null)
1. return -3
7. end if
8. search and find arc with key equal to tokey
9. if(tokey not found)
1. return -3
10.end if
11.set tovertex to arc destination
12.delete arc
13.decrement fromvertex outdegree
14.decrement tovertex indegree
15.return 1
end deletearc
f. Retrieve Vertex
 Retrieve vertex returns the data stored in a vertex
 Given the key of the vertex, the data are placed in the output area specified in
the call
Algorithm retrievevertex(graphkey, dataout)
Data contained in vertex is identified by key passed to caller
Pre graph is reference to a graph head structure
key is the key of the vertex data
dataout is reference todata variable
Post vertex data copied to dataout
-2 if key not found
1. if(empty graph)
1. return -2
2. end if
3. search for vertex
4. if(vertex found)
1. move locnptr data to dataout
46
CTR
2. return 1
5. else
1. return -2
6. end if
end retrievevertex
g. Depth first traversal

 It visits all vertices in a graph by processing a vertex and all of its descendents
before processing an adjacent vertex
 We implement the depth first traversal by using stack
 When we reach a vertex, we push its address into a stack.
 Then we pop the stack, process the vertex, and push all of its adjacent vertices
into the stack
 We must ensure that each vertex is processed only once
 When we created the structure for the vertex in algorithm, we included a
processed flag.
 When we begin the traversal we set the processed flag to 0
 When we push a vertex into the stack, we set its processed flag to 1, indicating
that it is in the stack, awaiting its turn
 This vertex, we set its flag to 2
 Now, if we arrive at a vertex more than once, we know that we either pushed it
or processed it earlier and not push or process it a second time
Algorithm depthfirst(graph)
Process the keys of the graph in depth first order
Pre graph is a pointer to a graph head structure
Post vertices “processed”
1. if(empty graph)
1. return
set processed flags to not processed
2. set walkptr to graph first
1. set processed to 0
4. end loop
process each vertex in list
5. createstack(stack)
6. loop(through vertex list)
1. if(vertex not processed and not in stack)
push and set flag to stack
1. pushstack(stack, walkptr)
47
CTR
2. set walkptr processed to 1

3. end if
process vertex at stack top
4. loop(not emptystack(stack))
1. set vertex to popstack(stack)
2. process(vertex)
3. set vertex to processed
push non – processed vertices from adjacency list
4. loop(through arc list)
1. if(arc destination not in stack)
1. pushstack(stack, destination)
2. set destination to in stack
2. end if
3. get next destination
5. end loop
5. end loop
2. end if
3. get next vertex
7. end loop
8. destroystack(stack)
end depthfirst
h. Breadth first traversal

 It processes a vertex and then processes all of its adjacent vertices
 We use a stack for the depth first traversal, we use a queue to traverse a graph
breadth first
Algorithm breadthfirst(graph)
Processes the keys of the graph in breadth – first order
Pre graph is pointer to graph head structure
Post vertices processed
1. if(empty graph)
1. return
2. end if
first set all processed flags to not processed
3. createqueue(queue)
1. set vertex to not procesed
5. end loop
48
CTR
process each vertex in vertex list

1. if(vertex not processed)
1. if(vertex not in queue)
Enqueue and set process flag to queued(1)
1. enqueue(queue, walkptr)
2. set vertex to enqueued
2. end if
Now process descendents of vertex at queue front
3. loop(not emptyqueue(queue))
1. set vertex to dequeue(queue)
Process vertex and flag as processed
2. process(vertex)
3. set vertex to processed
Enqueue non – processed vertices from adjacency list
4. loop(through adjacency list)
1. if(destination not enqueued or processed)
1. enqueue (queue, destination)
2. set destination to enqueued
2. end if
3. get next destination
5. end loop
4. end loop
2. end if
3. get next vertex
7. end loop
8. destroyqueue(queue)
end breadthfirst
I. Destroy graph
 The arcs are deleted when the corresponding vertex is deleted
Algorithm destroygraph(graph)
Traverses graph deleting all vertices and arcs
Pre nothing
Post all vertices and arcs deleted
1. if(empty graph)
1. return
2. loop(more vertices)
49
CTR
1. loop(vertex outdegree > 0)

1. delete vertex firstarc
2. subtract 1 from vertex outdegree
2. end loop
3. end loop
end destroy graph
50
CTR

Unit - V DS

Uploaded by

Copyright:

Available Formats

Unit - V DS

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit - V DS

Uploaded by

Copyright:

Available Formats

Data structures Lecture Notes Unit - V

 The concept of subtrees leads us to a recursive definition of a tree: a tree is a set

 It is used with algebraic expressions

 To convert a general tree to its parenthetical notation, we use the code as in

5.1.2 Binary trees

 To better understand the structure of binary tree, see the fig.

 The height of binary trees can be mathematically predicted

5.1.3 Binary tree traversals

Preorder Traversal (NLR)

1. If(root is not null)

 We are now ready to process the right subtree, D

Breadth first traversals

4. If(right subtree not null)

5.1.4 Applications of binary trees

2. the root and internal nodes are operators

 Three different expression formats: infix, postfix, and prefix

Pre tree is a pointer to an expression tree

General tree deletions

Changing a general tree to a binary tree

 In a general tree, we use two relationships

5.1.5 Binary search tree

 A Binary search tree is a binary tree with the following properties:

 Fig. contains five binary search tree

Binary search tree operations

1. Find the smallest node

2. Find the largest node

 Now let’s reverse the process

Algorithm searchBST(root, targetkey)

 We first added node 19

and call recursively to determine whether we are at a leaf yet

Algorithm addBST(root, newnode)

1. The node to be deleted has no children. In this case, all we need to do is

Algorithm deleteBST(root, dltkey)

2. else if(no right subtree)

5.1.6 Spanning Tree

 We can derive one or more spanning tree from a connected network

1. loop(through all edges)

 Two vertices are said to be connected if there is a path between them

 The degree of a vertex is the number of lines incident to it

 If the vertex is found its data are returned

5.2.3 Traverse graph

Breadth first traversal

 The BFT of a graph follows the same concept

Breadth first traversal of graph

In adjacency matrix representation, we use a vector to store the vertices and a

Limitation of adjacency matrix

5.2.5 Graph Algorithms

Post metadata elements have been initialized

Post vertex deleted(if degree zero)

g. Depth first traversal

2. set walkptr processed to 1

h. Breadth first traversal

process each vertex in vertex list

1. loop(vertex outdegree > 0)

You might also like