C++ Programming: Program Design Including Data Structures, 7th Edition Chapter 2

Question

C++ Programming: Program Design Including Data Structures, 7th Edition Chapter 20 PE #5

The algorithm to determine the minimal spanning tree given in this chapter is of the order O(n3).

The following is an alternative to Prim’s algorithm that is of the order O(n2).

Input: A connected weighted graph G=(V, E) of n vertices, numbered 0, 1, ..., n-1;

Starting with vertex s, with a weight matrix of W.

Output: The minimal spanning tree.

Prim2 (G, W, n, s)

Let T = (V, E), Where E = empty

For(j=0; j < n; j++)

{

edgeWeights[j] = W(s, j);

Edges[j] = s;

Visited[s] = false;

}

edgeWeights[s] = 0;

Visited[s] = true;

While[s] = true;

While(not all nodes are visited)

{

Choose the node that is not visited and has the smallest weight, and call it k.

Visited[k] = true;

E = E U { (k, edges[k]) }

V = V U { k }

For each node j that is not visited

If ( W(k, j) < edgeWeights[j])

{

edgeWeights[j] = W(k, j);

Edges[j] = k;

}

}

Return T;

Write a definition of the function Prim2 to implement this algorithm, and also add this function to the class msTreeType. Furthermore, write a program to test this version of Prim's algorithm

Thanks in advance

Explanation / Answer

import java.io.*;
import java.text.*;
import java.util.*;

public class MSTree extends Graph
{
protected int source;
protected double[][] weights;
protected int[] edges;
protected double[] edgeWeights;

  
public MSTree()
{
    super();
    weights = new double[maxSize][maxSize];
    edges = new int[maxSize];
    edgeWeights = new double[maxSize];
}

  
public MSTree(int size)
{
    super(size);

    weights = new double[maxSize][maxSize];
    edges = new int[maxSize];
    edgeWeights = new double[maxSize];
}  

   
public void createSpanningGraph() throws IOException, FileNotFoundException
{
   System.out.println("Create Spanning Graph");
}

public void minimalSpanning(int sVertex)
{
    int i,j,k;
    int startVertex = 0, endVertex = 0;
    double minWeight;

    source = sVertex;

    boolean[] mstv = new boolean[maxSize];

    for(j = 0; j < gSize; j++)
    {
        mstv[j] = false;
        edges[j] = source;
        edgeWeights[j] = weights[source][j];
    }

    mstv[source] = true;
    edgeWeights[source] = 0;

    for(i = 0; i < gSize - 1; i++)
    {
        minWeight = infinity;

        for(j = 0; j < gSize; j++)
            if(mstv[j])
                for(k = 0; k < gSize; k++)
                    if(!mstv[k] && weights[j][k] < minWeight)
                    {
                        endVertex = k;
                        startVertex = j;
                        minWeight = weights[j][k];
                        }
        mstv[endVertex] = true;
        edges[endVertex] = startVertex;
        edgeWeights[endVertex] = minWeight;
    }
    }
  
public void printTreeAndWeight()
{
    double treeWeight = 0;
    DecimalFormat twoDigits = new DecimalFormat("0.00");

    System.out.println("Source Vertex: " + source);
    System.out.println("Edges    Weight");

    for(int j = 0; j < gSize; j++)
    {
       if(edges[j] != j)
       {
          treeWeight = treeWeight + edgeWeights[j];
          System.out.println("(" + edges[j] + ", " + j + ")    "
                      + twoDigits.format(edgeWeights[j]));
        }
    }

    System.out.println();
    System.out.println("Minimal Spanning Tree Weight: "
                     + twoDigits.format(treeWeight));
}

public void Prim2(int i)
{
    int G;int W; int n = 0; int s = 0;
    boolean[] visited = null;

    for(int j=0;j<n;j++)
    {
        edgeWeights[j]=weights[s][j];
        edges[j]=s;
        visited[j]=false;

    }
    edgeWeights[s]=0;
    visited[s]=true;

    while(!visited[i]){
        int k = 0;
        visited[k]=true;
        for(int j=0;j<n;j++)
        if(weights[k][j])<edgeWeights[j])
        {
           edgeWeights[j] = weights[k][j]);
       Edges[j] = k;
      }

    }
   Return i;
   }

   Main.Class
   import java.io.FileNotFoundException;
   import java.io.IOException;

   public class Prim_Class
   {
   public static void main(String[]args)
   {
       MSTree myTree = new MSTree(8);
       try {
           myTree.createSpanningGraph();
          }
          catch (FileNotFoundException e)
       {
           // TODO Auto-generated catch block
           e.printStackTrace();
       }
       catch (IOException e)
       {
           // TODO Auto-generated catch block
           e.printStackTrace();
       }
     
       myTree.printGraph();
       myTree.printTreeAndWeight();
       myTree.minimalSpanning(2);
       myTree.printTreeAndWeight();
       myTree.Prim2(2);
       myTree.printTreeAndWeight();
       }
       }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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