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

what is the differance between minimum-weight spanning tree and heuristic spanning tree?

One of the basic motivations behind the Minimum Spanning Tree Problem is the goal of designing...

One of the basic motivations behind the Minimum Spanning Tree Problem is the goal of designing a spanning network for a set of nodes with minimum total cost. Here we explore another type of objective: designing a spanning network for which the most expensive edge is as cheap as possible. Specifically, let G = (V, E) be a connected graph with n vertices, m edges, and positive edges costs that are all distinct. Let T = (V, E0 ) be...

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)

Consider the Minimum Spanning Tree Problem on an undirected graph G=(V,E), with a cost ce ≥0...

Consider the Minimum Spanning Tree Problem on an undirected graph G=(V,E), with a cost ce ≥0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in general be many distinct minimum-cost solutions. Suppose we are given a spanning tree T ⊆ E with the guarantee that for every e ∈ T, e belongs to some minimum-cost spanning tree in G. Can we conclude that T itself must be a...

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

Binary Search Trees with Lazy Deletion Implement binary search tree class with lazy deletion that has...

Binary Search Trees with Lazy Deletion Implement binary search tree class with lazy deletion that has TreeNode as nested class in Java. Design the class, TreeNode to have following class variables: int key; // All Keys are in the range 1 to 99 TreeNode leftChild; TreeNode rightChild; boolean deleted; Your program method must have routines to do the following operations. 1. insert //Should insert a new element to a leaf node. If new element is aduplicatethen do nothing. If the...