Please write the complete code in C language which can work in Visual Studio 201

Question

Please write the complete code in C language which can work in Visual Studio 2015 without any errors

Write a C function that prints the minimum spanning tree of a graph. At the end,
print the weight of the spanning tree. A suggested report format is shown in the
following example.
Source Vertex To Vertex Weight
A B 2
A C 4
B D 3
D E 1
Total weight of spanning tree: 10
Your main program will read a graph from DataIn file to an adjacency table
before calling the function.

There is a 'skeleton code' given, so can someone just fill it up. It just needs to be filled up where it says add your code here, please try not to change the rest of the code

//Find out the minimum spanning tree (MST) of a graph which is stored in **AM1
//The MST will be stored in AM2.
//The output format should follow the specification

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define INFINITY   0
#define MAXNODE       26

// Pointer to the file you want to read and write.
FILE *fp;

int NumberOfNode = 0;

// Initialize the Adjacency table **AM
// In this function, you should set all elements in the Adjacency table to INFINITY
void InitAM(int **AM)
{
   //*********
   //Add your code here
   //*********
   //*********
}

//Read the Graph from the input file to **AM
//
int ReadGraph(int **AM)
{
   //open file
   fp = fopen ("DataIn.txt", "r");  
  
if (fp == NULL)
   {
       printf("Unable to open file.");
       return 0;
   }
   else
   {
       int i = 0;
       // get the number of nodes of the graph
       fscanf (fp, "%d ", &NumberOfNode);      
      
       for (;i< NumberOfNode;i++ )
       {
           int NodeOfLine = 0;
           int NumberOfNodesLine = 0;
           int node = 0;
           int weight = INFINITY;

//get the current node
           fscanf (fp, "%d", &NodeOfLine);

           if(NodeOfLine == (i+1))
           {
               int j=0;

               //get the number of nodes connected to the current node
               fscanf (fp, "%d", &NumberOfNodesLine);
          

               for (;j< NumberOfNodesLine;j++ )
               {
                   //get the weight of the link
                   fscanf (fp, "%d", &node);
                   fscanf (fp, "%d", &weight);
                   AM[i][node] = weight;                  
               }

               fscanf (fp, " ");              

           }
           else
           {
               return 0;
           }
       }
          
   }      
  
   fclose(fp);
   return 1;

}

//find the minimum spanning tree (MST) from **AM1, and store the MSP in **AM2
//
int MPS_tree(int **AM1,int **AM2)
{
   //*********
   //Add your code here
   //*********
   //*********

}

//print out the minimum spanning tree in **AM, as specified in Q4
//
void WriteMPS(int ** AM)
{
   //*********
   //Add your code here
   //*********
   //*********

}

///print out the graph in **AM, for testing
// In this function, all you have to do is to print every element in the Adjacency table **AM
//
void WriteGraph(int ** AM)
{
   //*********
   //Add your code here
   //*********
   //*********
}

int main( )
{
   //create two-dimensional array AM1, AM2
   //
   int ** AM1 = (int **) malloc( sizeof(int *) * MAXNODE );
   int ** AM2 = (int **) malloc( sizeof(int *) * MAXNODE );
   int i;
   for ( i = 0 ; i < MAXNODE ; i ++ )
   {
       AM1[i] = (int *) malloc( sizeof(int) * MAXNODE );
       AM2[i] = (int *) malloc( sizeof(int) * MAXNODE );
   }  

   InitAM(AM1);
   InitAM(AM2);

   if (ReadGraph(AM1) == 0)
   {
       return 1;
   }

   if(MPS_tree(AM1,AM2) == 0)
   {
       printf("There is no minimun spanning tree!");
       return 1;
   }

   WriteMPS( AM2 );

   for ( i = 0 ; i < MAXNODE ; i ++ )
   {
       free( AM1[i] );
       free( AM2[i] );
   }
   free(AM1);
   free(AM2);

   return 0;
}

Explanation / Answer

void KruskalMST(struct G* G)
{
int V = G->V;
struct ed Result[V]; // This will store the Resultant MST
int e = 0; // An index variable, used for Result[]
int i = 0; // An index variable, used for sorted eds

// Step 1: Sort all the eds in non-decreasing order of their weight
// If we are not allowed to change the given G, we can create a copy of
// array of eds
qsort(G->ed, G->E, sizeof(G->ed[0]), myComp);

// Allocate memory for creating V ssubsets
struct subset *subsets =
(struct subset*) malloc( V * sizeof(struct subset) );

// Create V subsets with single elements
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}

// Number of eds to be taken is equal to V-1
while (e < V - 1)
{
// Step 2: Pick the smallest ed. And increment the index
// for next iteration
struct ed next_ed = G->ed[i++];

int x = find(subsets, next_ed.src);
int y = find(subsets, next_ed.dest);

// If including this ed does't cause cycle, include it
// in Result and increment the index of Result for next ed
if (x != y)
{
Result[e++] = next_ed;
Union(subsets, x, y);
}
// Else discard the next_ed
}

// print the contents of Result[] to display the built MST
printf("Following are the eds in the constructed MST ");
for (i = 0; i < e; ++i)
printf("%d -- %d == %d ", Result[i].src, Result[i].dest,
Result[i].weight);
return;
}

here is the version of answer for asked question by try to store result of this in AM2 and then print it. It confusing with work your sample with file.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects