unit-2

Sets and disjoint set

By Dr K Thirupal Reddy
 Sets
• A set is a collection of distinct elements.
• A set is collections (things or objects)
• Object in a set are called elements or members.
• If it is member of a set S, then x in S, other wise x is not in S.
• Set Cardinality: The No. of elements in a set is called cardinality of size of a
set n(s).
Infinite set: A set contains infinite no of elements. +ve or –ve integers.
Empty set:
Subset: if every member of A also is a member of B. A is subset of B.
Equal Set:
Disjoint Sets:
• The disjoints are sets, those sets do not have any common
element .
Two sets A and B are said to be disjoint if there no
commone elements i.e., A  B =  .
Example:

1) S1={1,7,8,9},S2={2,5,10}, and S3={3,4,6}.

are three disjoint sets.
Union of Sets : AUB ={x: x in A and x in B}
Intersection of Sets : or
Difference of Sets : A-B ={x: x in A and x does not in B}
We identify a set by choosing a representative element of the set. It doesn’t
matter which element we choose, but once chosen, it can’t be changed.

Disjoint set operations:

FIND-SET(x): Returns the representative of the set
containing x.
UNION(i,j): Combines the two sets i and j into one new set. A new
representative is selected.
( Here i and j are the representatives of the sets )
Disjoint set Example
Make-Set(1)
Make-Set(2)
Make-Set(3 )
Make-Set(4)
Union(1,2)
Union(3,4)
Find-Set(2) return 1
Find-Set(4) return 3
Union(2,4)
up-tree.
• A simple data structure for implementing disjoint sets is the up-tree.
• DISJOINT SETS Consider a set
S={1,2,3,4,5,6,7,8,9,10}. These elements can be
partitioned into three disjoint sets.
• A = {1,2,3,6} B= {4,5,7} C= {8,9,10}
Each set can be represented as a tree. Notice
that for each set we have linked the nodes from
the children to the parent, rather than our usual
method of linking from parent to children.
Disjoint Set Operations:

• The disjoint set operations are

• 1. Union
• 2. Find
 UNION operation
• UNION(i,j) it means the elements of set i and elements of
set j are combined.
• If we want to represent UNION operation in the form of a
tree;
the UNION(i,j) i is parent ; j is the child.
• UNION of S1 and S2 S1US2
Let’s see how the union of these two
subsets looks like visually
Steps to perform union opration
Updation of P[i] valus for above
union opration.
• To obtain the union of two sets, all that has to be done is to
set the parent field of one of the roots to the other root.
This can be accomplished easily if with each set name, we
keep a pointer to the root of the tree representing the set.

Algorithm UNION(i,j)
{ //replace the disjoint sets with roots i and j.
integer i,j
P[j]:=i;
}
Time complxcity
• Since the time taken for a UNION is
constant, all the n-1 unions can be
processed in time O(n).
Find:
• Example:
• S1={1,7,8,9}
• Then, S2={2,5,10} S3={3,4,6}
• Find(4)= S3 Find(5)=S2 Find(7)=S1
Find Operation: To find the representative (root)

element of a subset that an element x belongs to that

set.

While the parent of x is not itself (indicating it's not the

representative), follow the parent pointers until you
reach the representative element.
Ex:1 Find 4 , it returns 1 ,because 4 is
present in tree so it return set
representative(root).
1 2 3 4 5

-1 1 1 3 1
Time Complexity
• Each find requires following chain of parent links from
node i to root. The time required to process a FIND for
an element at level i of a tree is O(i). Hence the total
time needed to process the n-2 finds is O(n2).
Weighted Union
• Weighted Union is a technique used in
Disjoint Set Data Structures to improve the
efficiency of union operations by considering
the size or rank of the sets being merged.
Weighted Union
• When performing a union between two
sets, you consider the sizes (number of
elements) of the two sets.
• You attach the root of the smaller set as a
child of the root of the larger set.
• This way, you ensure that the resulting
tree remains balanced, and the height of
the trees is reduced, leading to faster find
operations.
• Weighting Rule for UNION (i,j) If the number of nodes in a tree
i is less than the number in tree j, then make j the parent of i,
otherwise make i the parent of j. Both arguments of UNION
must be roots.
• To implement the weighting rule, we need to know how many
nodes are there in every tree.
•
• To do this easily, we maintain a count field in the root of every tree. If
i is a root node then count[i] equals the number of nodes in that tree.
• Since all the nodes other than the roots of trees have a positive
number in the P field, we can maintain the count in the P field of
roots as a negative number.
Weighted Union
Algorithm WeightedUnion(i,j)
// Union sets with roots i, and j, i ≠ j, using
// the weighting rule. p[i]= -count[i] and p[j]= -count[j].

{
temp:=p[ i ]+p[ j ];
if( p[ i ]>p[ j ] ) then
{ // i has fewer nodes.
p[i]:=j; p[j]:=temp;
}
else
{ // j has fewer or equal nodes.
p[ j ]:=i; p[ i ]:=temp;
}
}
Ex:-Consider the behavior of WeightedUnion on the following
sequence of unions starting from the initial configuration
p[i]= -count[i]= -1, 1≤ i ≤ 8=n .

Union(1,2), Union(3,4), Union(5,6), Union(7,8),

Union(1,3), Union(5,7), Union(1,5)
 [- 4] [- 4]

1 5

2 3 6 7

4 8

c) height-3 trees following Union(1,3), and (5,7)

[- 8]
1

2 3 5

4 6 7
d) height-4 tree following Union(1,5)

8
collapsing find
• The main idea of collapsing find is if the
immediate parent of an element isn't the
head of the subset, then find the subset and
collapse the element by setting its
immediate parent to the head of the subset.
• If j is a node on the path from i to its root
and p[i] is not equal to root[i] then set p[j] to
root[i].
Collapsing Find
Binary Tree Traversal Techniques

•Binary tree
• Binary trees are hierarchical data
structures composed of nodes where
each node has at most two children, a
left child and a right child. There are
three primary binary tree traversal
techniques
Binary Tree Traversal Techniques
• The term 'tree traversal' means traversing or
visiting each node of a tree. There is a single way
to traverse the linear data structure such as linked
list, queue, and stack. Whereas, there are multiple
ways to traverse a tree that are listed as follows.
• Preorder traversal
• Inorder traversal
• Postorder traversal
Preorder traversal
• This technique follows the 'root left right'
policy. It means that, first root node is visited
after that the left subtree is traversed
recursively, and finally, right subtree is
recursively traversed. As the root node is
traversed before (or pre) the left and right
subtree, it is called preorder traversal
1.Visit the root.
2.Traverse the left sub tree of root.
3.Traverse the right sub tree of root.
Ex:
• preorder(node):
• if node is not null:
• visit(node)
• preorder(node.left)
• preorder(node.right)
Inorder traversal
This technique follows the 'left root right' policy.
It means that first left subtree is visited after
that root node is traversed, and finally, the
right subtree is traversed. As the root node is
traversed between the left and right subtree, it
is named inorder traversal.

1.Traverse the left most sub tree.

2.Visit the root.
3.Traverse the right most sub tree.
• inorder(node):
• if node is not null:
• inorder(node.left)
• visit(node)
• inorder(node.right)
Postorder traversal
• This technique follows the 'left-right root' policy. It
means that the first left subtree of the root node is
traversed, after that recursively traverses the right
subtree, and finally, the root node is traversed. As
the root node is traversed after (or post) the left
and right subtree, it is called postorder traversal

1.Traverse the left sub tree of root.

2.Traverse the right sub tree of root.
3.Visit the root.
• postorder(node):
• if node is not null:
• postorder(node.left)
• postorder(node.right)
• visit(node)
spanning trees
• Spanning tree is a subgraph of a given graph
that includes all the vertices of the original
graph while maintaining connectivity and
without forming any cycles.
• A spanning tree of an undirected graph with N
vertices will have exactly N-1 edges. This
minimizes the number of edges while
maintaining connectivity.
• vertices are reachable from a designated root vertex,
KRUSKAL’S ALGORITHM
• Step 1 : Arrange all the edges in ascending order based on cost
• Step 2 : Consider least cost weighted edge and include it in tree. If
that edge forms a cycle just ignore and consider next least cost
weighted edge
• Step 3 : Repeat Step-2 until all the vertices are included in the tree
PRIM’S ALGORITHM
Graph should be weighted , connected and undirected

• Step 1 : Select any vertex

• Step 2 : Find all the edges from selected vertex to all new vertices.
Select least weighted edge and include it in tree. If the edge can form
a cycle, then discard it and consider next least weighted edge and
include it in the tree.
• Step 3 : Repeat step-2 until all the vertices are included in the tree.
BREATH-FIRST SEARCH
• Step 1 : Define a queue of size is total number of vertices in the graph
• Step 2 : select any vertices as starting point for traversal. Visit that
vertex and insert it into queue.
• Step 3 : visit all the adjacent vertices of the vertex which is at front of
the queue which is not visited and insert them into queue.
• Step 4 : when there is no new vertex to be visit from the vertex at
front of the queue then delete that vertex from the queue.
• Step 5 : Repeat step 3 and 4 until queue becomes empty
DEPTH-FIRST SEARCH
• Step 1 : Select the vertex A as the Starting point, that A can be push
into the stack.
• Step 2 : Visit any adjacent vertex of A, which is not visited(B) push
newly visited vertex B on to the stack.
• Step3: Visit any adjacent vertex of B, Which is not visited (C) push C
on to the stack.
• Step4 :repeat this process until reach all the vertices.
•The choice between DFS and BFS depends
on the specific problem you're trying to
solve and the characteristics of the graph.
•DFS is typically used when you want to
explore deeply into a graph
•while BFS is used when you want to explore
broadly or find the shortest path. Both
algorithms are essential tools for graph
analysis and are widely used in computer
science and various applications.
Depth-First Search (DFS)
•DFS explores as far as possible along
a branch before backtracking. It uses
a stack (or recursion) to keep track of
vertices to visit. Here's a basic outline
of how DFS works.
Basic outline of how DFS works
• Start at an initial vertex.
• Visit the vertex and mark it as visited.
• Explore one unvisited adjacent vertex (choose
any), and repeat the process recursively.
• If there are no unvisited adjacent vertices,
backtrack to the previous vertex.
• Repeat steps 2-4 until all vertices have been
visited.
• DFS is often used to find paths and cycles in a
Step1: Initially stack and visited arrays
are empty.
Step 2: Visit 0 and put its adjacent nodes
which are not visited yet into the stack.
Step 3: Now, Node 1 at the top of the stack, so visit
node 1 and pop it from the stack and put all of its
adjacent nodes which are not visited in the stack
Now, Node 2 at the top of the stack, so visit node 2
and pop it from the stack and put all of its adjacent
nodes which are not visited (i.e, 3, 4) in the stack.
Step 5: Now, Node 4 at the top of the stack, so visit
node 4 and pop it from the stack and put all of its
adjacent nodes which are not visited in the stack.
Step 6: Now, Node 3 at the top of the stack, so
visit node 3 and pop it from the stack and put all of
its adjacent nodes which are not visited in the stack
DFS algorithm
1.First, create a stack with the total number of vertices
in the graph.
2.Now, choose any vertex as the starting point of
traversal, and push that vertex into the stack.
3.After that, push a non-visited vertex (adjacent to the
vertex on the top of the stack) to the top of the stack.
4.Now, repeat steps 3 and 4 until no vertices are left
to visit from the vertex on the stack's top.
5.If no vertex is left, go back and pop a vertex from
the stack.
6.Repeat steps 2, 3, and 4 until the stack is empty
DFS algorithm
1. function nonRecursiveDFS(graph, startNode):
2. stack = empty_stack() // Initialize an empty stack
3. visited = set() // Initialize an empty set to keep track of visited nodes
4.
5. stack.push(startNode) // Push the start node onto the stack
6.
7. while stack is not empty:
8. currentNode = stack.pop() // Pop the top node from the stack
9.
10. if currentNode is not in visited:
11. visited.add(currentNode) // Mark the current node as visited
12.
13. // Process the current node (e.g., print it or perform some
operation)
14. process(currentNode)
15.
16. // Push unvisited neighboring nodes onto the stack
17. for neighbor in graph.neighbors(currentNode):
18. if neighbor is not in visited:
Breadth-First Search (BFS).
•BFS explores vertices level by level,
starting from the source vertex and
moving outward.
•It is uses a queue to keep track of
vertices to visit
• BFS is often used to find the shortest
path in unweighted graphs and to
perform level-order traversals.
Basic outline of how BFS works
• Start at an initial vertex.
• Visit the vertex and mark it as visited.
• Enqueue all unvisited adjacent vertices.
• Dequeue the next vertex from the queue and
repeat the process.
• Continue dequeuing and enqueuing until the
queue is empty
Initially queue and visited arrays are
empty.
Step2: Push node 0 into queue and
mark it visited.
Remove node 0 from the front of queue and visit
the unvisited neighbours and push them into queue.
Step 4: Remove node 1 from the front of queue
and visit the unvisited neighbours and push them
into queue
Step 5: Remove node 2 from the front of
queue and visit the unvisited neighbours
and push them into queue
• Step 6: Remove node 3 from the front of
queue and visit the unvisited neighbours and
push them into queue.
As we can see that every neighbours of node 3
is visited, so move to the next node that are in
the front of the queue.
• Steps 7: Remove node 4 from the front of queue
and visit the unvisited neighbours and push them
into queue.
As we can see that every neighbours of node 4
are visited, so move to the next node that is in
the front of the queue. Now, Queue becomes empty,
So, terminate these process of iteration
 Algorithm
1.Start by putting any one of the graph's
vertices at the back of a queue.
2.Take the front item of the queue and add it
to the visited list.
3.Create a list of that vertex's adjacent nodes.
Add the ones which aren't in the visited list
to the back of the queue.
4.Keep repeating steps 2 and 3 until the
queue is empty.
• Algorithm

• Step 1: SET STATUS = 1 (ready state) for each node in

G
• Step 2: Enqueue the starting node A and set its STATUS
= 2 (waiting state)
• Step 3: Repeat Steps 4 and 5 until QUEUE is empty
• Step 4: Dequeue a node N. Process it and set its
STATUS = 3 (processed state).
• Step 5: Enqueue all the neighbours of N that are in the
ready state (whose STATUS = 1) and set their STATUS =
2(waiting state)[END OF LOOP]
• Step 6: EXIT
• def bfs(graph, start_node):
• # Create a queue and mark the start node as visited
• queue = []
• visited = set()
• queue.append(start_node)
• visited.add(start_node)

• while queue:
• # Dequeue a node and process it
• current_node = queue.pop(0)
• print(current_node)

• # Explore neighboring nodes

• for neighbor in graph[current_node]:
• if neighbor not in visited:
• queue.append(neighbor)
• AND-OR GRAPHS

• The AND-OR GRAPH (or tree) is useful for representing the

solution of problems that can solved by decomposing them into a
set of smaller problems, all of which must then be solved.
• This decomposition, or reduction, generates arcs that we call
AND arcs. One AND arc may point to any number of successor
nodes, all of which must be solved in order for the arc to point to
a solution.
• Just as in an OR graph, several arcs may emerge from a single
node, indicating a variety of ways in which the original problem
might be solved. This is why the structure is called not simply an
AND-graph but rather an AND-OR graph (which also happens to
be an AND-OR tree)
EXAMPLE FOR AND-OR GRAPH
Game Tree
• A game tree is a tree like structure, that represent all possible states
and moves of a game from initial state to terminal state.
Connected & Bi-connected
components with Examples
• Bi-connected Components: