Java while loop mysterious iteration

Question

Can somebody teach me how the while loop in find method is working? Does that somehow iterates the parent array from 0 to the endpoint automatically? until paren[i] != i?

static int find(int i) 
{ 
    while (parent[i] != i) 
        i = parent[i]; 
    return i; 
} 
  
// Finds MST using Kruskal's algorithm 
static void kruskalMST(int cost[][]) 
{ 
    int mincost = 0; // Cost of min MST. 
  
    // Initialize sets of disjoint sets. 
    for (int i = 0; i < V; i++) 
        parent[i] = i; 
  
    // Include minimum weight edges one by one 
    int edge_count = 0; 
    while (edge_count < V - 1) 
    { 
        int min = INF, a = -1, b = -1; 
        for (int i = 0; i < V; i++) 
        { 
            for (int j = 0; j < V; j++)  
            { 
                if (find(i) != find(j) && cost[i][j] != 0 && cost[i][j] < min)  
                { 
                    min = cost[i][j]; 
                    a = i; 
                    b = j; 
                } 
            } 
        }

user13784117 · Accepted Answer · 2020-06-22 12:03:21Z

2

It's difficult to see what you're not grasping - it executes as written.

find is called with some value of i

Does the i'th entry in the parent array contain the value i? Yes, then control proceeds to the return statement and we're done.

Otherwise, set the value in i to the value from the i'th entry of the 'parent' array.

Does the i'th entry in the parent array contain the value i?
Yes, then control proceeds to the return statement and we're done.

Otherwise, set the value in i to the value from the i'th entry of the 'parent' array.

… and keep doing this ...

The overall logic seems to be that each entry in the parent array is supposed to identify its parent entry, except that the topmost entry has itself for its parent.

However, since all entries in parent are initialized such that the i'th entry contains i, and nothing changes that, it seems the code shown is incomplete.

edited Jun 22, 2020 at 12:03

answered Jun 21, 2020 at 23:50

user13784117

1,1426 silver badges4 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java while loop mysterious iteration

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related