Suppose a social network, N, contains n people, m edges, and c connected compone

Question

Suppose a social network, N, contains n people, m edges, and c connected components. What is the exact number of times that each of the methods, makeSet, union, and find, are called in computing the connected components for N using Algorithm 7.2?

Algorithm 7.2: A connected components algorithm using union and find.

ConnectedComponents(S,E): Input: A set, S, of n people and a set, E, of m pairs of people from S defining pairwise relationships Output: An identification, for each x in S, of the connected component containing x for each x in S do makeSet(x) for each (x, y) in E do if find(x) = find(y) then union(find(x), find(y)) for each x in S do Output “Person x belongs to connected component” find(x)

Explanation / Answer

if n is a singleton set then the

union() operation will run about (log n) times and both find() and makeSet() will run n times

that is if n =1000 then

find() and makeSet() will run for 1000 times

where as union() will run only 3 times;

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.