Question

In: Computer Science

Java programming Trace the algorithm for minimum spanning tree (eager, lazy Prim algorithm)

Java programming
Trace the algorithm for minimum spanning tree (eager, lazy Prim algorithm)

Solutions

Expert Solution

import java.util.InputMismatchException;

```
import java.util.Scanner;
```
```
 
```
```
public class Prims
```
```
{
```
```
    private boolean unsettled[];
```
```
    private boolean settled[];
```
```
    private int numberofvertices;
```
```
    private int adjacencyMatrix[][];
```
```
    private int key[];
```

    public static final int INFINITE = 999;

```
    private int parent[];
```
```
    public Prims(int numberofvertices)
```
```
    {
```

        this.numberofvertices = numberofvertices;

        unsettled = new boolean[numberofvertices + 1];

        settled = new boolean[numberofvertices + 1];

        adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];

        key = new int[numberofvertices + 1];

        parent = new int[numberofvertices + 1];

```
    }
```

   public int getUnsettledCount(boolean unsettled[])

```
    {
```
```
        int count = 0;
```

        for (int index = 0; index < unsettled.length; index++)

```
        {
```
```
            if (unsettled[index])
```
```
            {
```
```
                count++;
```
```
            }
```
```
        }
```
```
        return count;
```
```
    }
```
```
 
```

    public void primsAlgorithm(int adjacencyMatrix[][])

```
    {
```
```
        int evaluationVertex;
```

        for (int source = 1; source <= numberofvertices; source++)

```
        {
```

            for (int destination = 1; destination <= numberofvertices; destination++)

```
            {
```

                this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];

```
            }
```
```
}
```

for (int index = 1; index <= numberofvertices; index++)

```
        {
```
```
            key[index] = INFINITE;
```
```
        }
```
```
        key[1] = 0;
```
```
        unsettled[1] = true;
```
```
        parent[1] = 1;
```
```
 
```

        while (getUnsettledCount(unsettled) != 0)

```
        {
```

            evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);

            unsettled[evaluationVertex] = false;

            settled[evaluationVertex] = true;

            evaluateNeighbours(evaluationVertex);

```
        }
```
```
    } 
```

 private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)

```
    {
```
```
        int min = Integer.MAX_VALUE;
```
```
        int node = 0;
```

        for (int vertex = 1; vertex <= numberofvertices; vertex++)

```
        {
```

            if (unsettled[vertex] == true && key[vertex] < min)

```
            {
```
```
                node = vertex;
```
```
                min = key[vertex];
```
```
            }
```
```
        }
```
```
        return node;
```
```
    }
```

public void evaluateNeighbours(int evaluationVertex)

```
    {
```
```
 
```

        for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)

```
        {
```

            if (settled[destinationvertex] == false)

```
            {
```

                if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)

```
                {
```

                    if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])

```
                    {
```

                        key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];

                        parent[destinationvertex] = evaluationVertex;

```
                    }
```

                    unsettled[destinationvertex] = true;

```
                }
```
```
            }
```
```
        }
```
```
    }
```
```
public void printMST()
```
```
    {
```

        System.out.println("SOURCE  : DESTINATION = WEIGHT");

        for (int vertex = 2; vertex <= numberofvertices; vertex++)

```
        {
```

            System.out.println(parent[vertex] + "\t:\t" + vertex +"\t=\t"+ adjacencyMatrix[parent[vertex]][vertex]);

```
        }
```
```
public static void main(String... arg)
```
```
    {
```
```
        int adjacency_matrix[][];
```
```
        int number_of_vertices;
```

        Scanner scan = new Scanner(System.in);

```
 
```
```
        try
```
```
        {
```

            System.out.println("Enter the number of vertices");

            number_of_vertices = scan.nextInt();

            adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];

```
 
```

            System.out.println("Enter the Weighted Matrix for the graph");

            for (int i = 1; i <= number_of_vertices; i++)

```
            {
```

                for (int j = 1; j <= number_of_vertices; j++)

```
                {
```

                    adjacency_matrix[i][j] = scan.nextInt();

```
                    if (i == j)
```
```
                    {
```

                        adjacency_matrix[i][j] = 0;

```
                        continue;
```
```
}
```

                    if (adjacency_matrix[i][j] == 0)

```
                    {
```

                        adjacency_matrix[i][j] = INFINITE;

```
                    }
```
```
                }
```
```
            }
```
```
 
```

            Prims prims = new Prims(number_of_vertices);

            prims.primsAlgorithm(adjacency_matrix);

```
            prims.printMST();
```
```
 
```

        } catch (InputMismatchException inputMismatch)

```
        {
```

            System.out.println("Wrong Input Format");

```
        }
```
```
        scan.close();
```
```
    }
```
```
}
```
```
    }
```

venereology answered 1 year ago

Next > < Previous

Question

Java programming Trace the algorithm for minimum spanning tree (eager, lazy Prim algorithm)

Solutions

Expert Solution

Related Solutions

Prove that Kruskal’s algorithm finds a minimum weight spanning tree.

Give the entire code for Minimum spanning tree using Boruvka's algorithm in java (not copy-pasted from...

Suppose T is a minimal spanning tree found by Prim’s algorithm in a connected graph G....

Programming language: JAVA First, implement a recursive, Divide&Conquer-based algorithm to identify both the Minimum and Maximum...

minimum spanning tree: find a connected subgraph whose total edge cost is minimized (python code)

AVL tree; Insert and Range Minimum operation in Java code.

In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem. (a)...

Show that a breadth-first spanning tree contains the shortest paths be- tween the root to every...

Develop a recursive algorithm to find the smallest and largest element in an array and trace...

This for Java Programming Write a java statement to import the java utilities. Create a Scanner...