I AM LOOKING ONLY FOR ONE C++ FUNCTION PLEASE Write an algorithm that, given two

Question

I AM LOOKING ONLY FOR ONE C++ FUNCTION PLEASE

Write an algorithm that, given two nodes of a graph, uses the ideas of partitioning sets as given below to determine if the two nodes are connected. Initialize Partition (N) {for i = 1 to N do Parent[i] = -1 end do} FindRoot (s) {result = s while Parent[result] > 0 do result = Parent[result] end while return result} Union (i, j) {//i, j - the partitions to join together totalElements = Parent[i] + Parent [j] if Parent[i] greaterthanorequalto Parent[j] then Parent[i] = j Parent[j] = totalElements else Parent[j] = i Parent[i] = totalElements end if}

Explanation / Answer

In an undirected graph, according to the above array implementation, we can say that two nodes are connected if they have same root. Approach is to find roots of the given nodes and if they are same we can say those two nodes are connected else not connected.

int IsConnected(a,b) //Two nodes a,b
{
roota = FindRoot(a);
rootb = FindRoot(b);
if(roota == rootb) //Nodes are in the same tree
{
return 1;
}
else
{
return 0;
}
}

Above code is only implementation of the function which checks for the connectivity of the nodes in the graph. Function can be executed only if we implement the structure of tree.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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