Question

IN JAVA

Given is a weighted undirected graph G = (V, E) with positive weights and a subset of its edges F E. ⊆ E. An F-containing spanning tree of G is a spanning tree that contains all edges from F (there might be other edges as well). Give an algorithm that finds the cost of the minimum-cost F-containing spanning tree of G and runs in time O(m log n) or O(n2).

Input: The first line of the text file in input stores n and m. The following lines store data about edges (u, v) in order u, v, weight, 0 or 1. It writes 0 if the edge is not in the set F, 1 otherwise.

Output: Only one value, the cost of the tree or -1 if there is no such tree. The output is written to Java standard output.

Answer 1

Program:

File name: "Graph.java"

Output 1:

Output 2:

Editable code:

//Import necessary header files
import java.util.*;

//Define the class "Graph"
public class Graph
{
//Declare and initialize the necessary variables
public int isVisited[] = new int[15];
public int cost[][] = new int[10][10];
int tot=0;
public int min_cost;

//Define the function "calculate()"
public void calculate(int n)
{
//Declare and initialize the necessary variables
int flag[] = new int[n+1];
int a,b,min=999,num_edges=1,c=1,d=1,minpos_a=1,minpos_b=1;

//Check the condition
while(num_edges < n)
{
//For loop to iterate the cost matrix   
for(a=1,min=999;a<=n;a++)
for(b=1;b<=n;b++)
  
//Check the node cost is less than minimum cost
if(this.cost[a][b]<min)
  
//Check the node is not visited
if(this.isVisited[a]!=0)
{
//True, assign the cost as minimum cost
min=this.cost[a][b];
  
//Assign the value to "c"
c=minpos_a=a;
  
//Assign the value to "d"
d=minpos_b=b;
}
  
//Check the condition
if(this.isVisited[minpos_a]==0 || this.isVisited[minpos_b]==0)
{
//True, assign the value of "min" to "tot"
tot+=min;
  
//Add the value to "min_cost"
this.min_cost=this.min_cost+min;
  
//Incrememt the edges by "1"
num_edges=num_edges+1;
  
//Initialize the value
this.isVisited[d]=1;
}
  
//Initialize the value
this.cost[c][d]=this.cost[d][c]=999;   
}
  
//Print the cost of the tree
System.out.println("cost of the tree is: "+tot);
}

//Define the "main()" function
public static void main(String args[])
{
//Declare the necessary variables
int nodes,a,b;
  
//Scanner method to get the input from the user
Scanner in = new Scanner(System.in);
  
//Print the statement
System.out.println("Enter the Number of Nodes \n");
  
//Get the number of nodes from the user
nodes = in.nextInt();
  
//Create object for the class "Graph"
Graph g = new Graph();
  
//If the tree is empty
if (nodes == 0)
{
//Print the message
System.out.println("Cost of the tree is:-1, there is no such tree.");
}
  
//Otherwise
else
{
//Print the cost of the tree
System.out.println("Enter the Cost Matrix Weights : \n");
  
//Loop to get the cost matrix
for(a=1;a<=nodes;a++)
for(b=1;b<=nodes;b++)
{
//Get the value from the user
g.cost[a][b]=in.nextInt();
  
//If the node value is equal to zero
if(g.cost[a][b]==0)
  
//Then, initialize the value
g.cost[a][b]=999;
}
  
//Initialize the value
g.isVisited[1]=1;
  
//Call the function "calculate()"
g.calculate(nodes);
}
}   
}