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)

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 2 years ago

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...

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

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

Suppose T is a minimal spanning tree found by Prim’s algorithm in a connected graph G. (i) Show that either T contains the n-1 smallest edges, or the n-1 smallest edges form a subgraph which contains a cycle. (ii) Show that if an edge (a, b) is not in T and if P is the unique path in T from a to b, then for each edge e in P the weight of e is less than the weight of...

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

Programming language: JAVA First, implement a recursive, Divide&Conquer-based algorithm to identify both the Minimum and Maximum element in an unsorted list. Second, convert your recursive algorithm to a non-recursive (or iterative) implementation. For your input, populate an "unsorted list" with random elements between 1 and 1,000,000.

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)...

In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem. (a) No fraction allowed Max Weight W= 9 item 1: profit $20, weight 2, prof/weight=$10 item 2: profit $30, weight 5, prof/weight=$6 item 3: profit $35, weight 7, prof/weight=$5 item 4: profit $12, weight 3, prof/weight=$4 item 5: profit $3, weight 1, prof/weight=$3

IN JAVA Given a binary search tree, extract min operation finds the node with minimum key...

IN JAVA Given a binary search tree, extract min operation finds the node with minimum key and then takes it out of the tree. The program can be C++/Java or C-style pseudocode. Do not use function call to either Min or delete done in the class. Write this from scratch. (No need to ensure AVL properties, just show it for a generic BST) Node * extract min(Node * x) { }

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

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

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

Develop a recursive algorithm to find the smallest and largest element in an array and trace the recursive function with appropriate message. using c++ add comment to the code