9
Tôi đang cố gắng viết một chương trình có thể tìm thấy cây bao trùm tối thiểu. Nhưng một vấn đề tôi gặp phải với thuật toán này, là thử nghiệm cho một mạch. Điều gì sẽ là cách tốt nhất để làm điều này trong java.Kiểm tra mạch khi thực hiện thuật toán Kruskalls
Ok đây là mã của tôi
import java.io.*;
import java.util.*;
public class JungleRoads
{
public static int FindMinimumCost(ArrayList graph,int size)
{
int total = 0;
int [] marked = new int[size]; //keeps track over integer in the mst
//convert an arraylist to an array
List<String> wrapper = graph;
String[] arrayGraph = wrapper.toArray(new String[wrapper.size()]);
String[] temp = new String[size];
HashMap visited = new HashMap();
for(int i = 0; i < size; i++)
{
// System.out.println(arrayGraph[i]);
temp = arrayGraph[i].split(" ");
//loop over connections of a current node
for(int j = 2; j < Integer.parseInt(temp[1])*2+2; j++)
{
if(temp[j].matches("[0-9]+"))
{
System.out.println(temp[j]);
}
}
}
graph.clear();
return total;
}
public static void main(String[] args) throws IOException
{
FileReader fin = new FileReader("jungle.in");
BufferedReader infile = new BufferedReader(fin);
FileWriter fout = new FileWriter("jungle.out");
BufferedWriter outfile = new BufferedWriter(fout);
String line;
line = infile.readLine();
ArrayList graph = new ArrayList();
do
{
int num = Integer.parseInt(line);
if(num!= 0)
{
int size = Integer.parseInt(line)-1;
for(int i=0; i < size; i++)
{
line = infile.readLine();
graph.add(line);
}
outfile.write(FindMinimumCost(graph, size));
}
line = infile.readLine();
}while(!line.equals("0"));
}
}
Đúng tôi nếu tôi sai nhưng đây là một cái cây, vì vậy tất cả các nút trừ nút đầu tiên sẽ có một nút cha. Bạn đã xem xét việc triển khai này chưa. –
@Legend, Trong thuật toán của kruskall, trong thời gian chạy thuật toán, chúng ta có rừng không phải cây, vì vậy giả thiết của bạn là sai. –