// Open the edges file for output to gnuplot file2 = fopen("/home/bill/LinuxVerOfWin7/Temp/gnuplotedges.txt", "w"); StartTime = (double) clock() / CLOCKS_PER_SEC; // Will time how long it takes to solve problem. NbrVrtx1 = NbrVrtx - 1; TotalTreeDist = 0.0; for (i = NbrVrtx1; i ; i--) // Initialize array for solve Dist2Tree[i] = 1.0E50; // Initially only the last vertex is in the tree InTree[NbrVrtx] = 1; // Alternately, wouldn't need this array if Dist2Tree[i] // were to be set to -1.0 at end of "i" loop and then test // the distance to see if vertex is in the tree, // but the code using "Intree[]" looks better. LastAddedVrtx = NbrVrtx; // All others are not in the tree for ( i = NbrVrtx1; i; i--) { // For all other vertices to be added to the tree. XcoordOfLastAdded = Xcoord[LastAddedVrtx]; // The coordinates for the "Last added" vertex YcoordOfLastAdded = Ycoord[LastAddedVrtx]; MinDist2Tree = 1.0e50; // For all vertices that are not in the tree yet for ( j = NbrVrtx1; j; j--) { // Update the distance to the tree for the new vertex // Will also look for the closest distance of the // "not in tree vertices" to those that are in the tree if (InTree[j]) // If Vertex is already in the tree, continue; // ignore other calcs. // Check all vertices not in the tree to see if the most // recent tree vertex reduces distance to the tree DeltaX = Xcoord[j] - XcoordOfLastAdded; // (Actual dist. is sqrt. of value used in calcs.) DeltaY = Ycoord[j] - YcoordOfLastAdded; // (But don't need sqrt() so save a few calcs.) Dist2LastAdded = DeltaX * DeltaX + DeltaY * DeltaY; if (Dist2LastAdded < Dist2Tree[j]) { // If the most recently added vertex to the tree Dist2Tree[j] = Dist2LastAdded; // needs updating, then update this info ClosestTreeVrtx[j] = LastAddedVrtx; } // Also check to see which of all the vertices that are if (Dist2Tree[j] < MinDist2Tree) { // not in the tree should be added next. MinDist2Tree = Dist2Tree[j]; ClosestCandidateVrtx = j; ClosestInTreeVrtx = ClosestTreeVrtx[j]; } } // At this point we know which new vertex to add to the tree. InTree[ClosestCandidateVrtx] = 1; // Add this closest candidate vertex to the tree LastAddedVrtx = ClosestCandidateVrtx; TotalTreeDist += sqrt(MinDist2Tree); // Output this edge to gnuplot to display graph fprintf(file2, "%8.2f %8.2f\n", Xcoord[ClosestCandidateVrtx], Ycoord[ClosestCandidateVrtx]); // X,Y coords for one end fprintf(file2, "%8.2f %8.2f\n\n", Xcoord[ClosestInTreeVrtx], Ycoord[ClosestInTreeVrtx]); // X,Y coords for other end } fclose(file2); EndTime = (double) clock() / CLOCKS_PER_SEC; printf("Total length of minimal spanning tree = %g\n", TotalTreeDist); printf("Solution time = %g seconds\n", EndTime - StartTime); PauseMsg();