title: C Implementation of Kruskal's algorithm for MST
body: <p>I was studying Kruskal's algorithm for finding the MST for a given graph and i understand the basic concept that you have to consider all the vertices as a forest initially. After that you have to find the minimum edge and joining the vertices of the edge into one tree. And doing this recursively until only one tree containing all the vertices is left.</p>
  
  <p>And i came across the following implementation of this algorithm.</p>
  
  <pre><code>#include&lt;iostream.h&gt;
  
  int p[10];
  
  void kruskal(int w[10][10],int n)
  {
      int min,sum=0,ne=0,i,j,u,v,a,b;
      for(i=1;i&lt;=n;i++)
      p[i]=0;
      while(ne&lt;n-1)
      {
          min=999;
          for(i=1;i&lt;=n;i++)
          for(j=1;j&lt;=n;j++)
          {
              if(w[i][j]&lt;min)
              {
                      min=w[i][j];
                  u=a=i;
                  v=b=j;
              }
          }
          while(p[u])
              u=p[u];
          while(p[v])
              v=p[v];
          if(u!=v)
          {
              ne++;
              sum+=min;
              cout&lt;&lt;"\nedge "&lt;&lt;a&lt;&lt;"--&gt;"&lt;&lt;b&lt;&lt;" is "&lt;&lt;min;
              p[v]=u;
          }
          w[a][b]=w[b][a]=999;
      }
      cout&lt;&lt;"\nmin cost spanning tree= "&lt;&lt;sum;
  }
  
  void main()
  {
      int w[10][10],n,i,j;
      clrscr();
      cout&lt;&lt;"enter no.of vertices\n";
      cin&gt;&gt;n;
      cout&lt;&lt;"enter weight matrix\n";
      for(i=1;i&lt;=n;i++)
          for(j=1;j&lt;=n;j++)
              cin&gt;&gt;w[i][j];
      for(i=1;i&lt;=n;i++)
          for(j=1;j&lt;=n;j++)
              if(w[i][j]==0)
                  w[i][j]=999;
      kruskal(w,n);
  }
  </code></pre>
  
  <p>What i don't understand is the need for:</p>
  
  <pre><code>while(p[u])
      u=p[u];
  while(p[v])
      v=p[v];
  </code></pre>
  
  <p>What exactly do those two while loops do?</p>
  
  <p>edit: and also the necessity of-</p>
  
  <pre><code>for(i=1;i&lt;=n;i++)
          for(j=1;j&lt;=n;j++)
              if(w[i][j]==0)
                  w[i][j]=999; 
  </code></pre>