我从老师那里得到了一些输入文件,我们应该用它们来测试程序。任务是从文件中读取,创建有向图并打印输出。但如果存在循环,我们应该终止程序。
我有一些名为 house1 和 house2 的文件。在文件 house1 中没有任何循环,但在 house2 中有。但我不明白为什么我的程序找不到那个循环。 这里我有所有的代码,并且任何说明我应该在哪里查看的帮助都会得到提示:)
import java.util.*;
import java.io.*;
import java.lang.*;
class Input {
public static void main(String[] args) {
if (args.length == 0) {
System.out.println("enter a filename!");
System.exit(1);
} else if (args.length == 1) {
String fil = args[0]+".txt";
LesFraFil(fil);
// skrivUt();
topSort();
} else {
System.out.println("too many parameters, try again...");
}
}
static int antTask;
static Task[] ids;
static int tTid;
static void LesFraFil(String fil) {
int i = 0;
int j;
try {
String lest;
Scanner in = new Scanner(new FileReader(fil));
Edge til;
int counter = 0;
antTask = in.nextInt();
ids = new Task[antTask];
System.out.println(antTask);
while (in.hasNextLine()) {
lest = in.nextLine();
// hvis tom linje, så hopper den over
if(lest.trim().length() == 0) continue;
String split[] = lest.split("\\s+");
int id = Integer.parseInt(split[0]);
String act = split[1];
int tid = Integer.parseInt(split[2]);
int staff = Integer.parseInt(split[3]);
int depA = Integer.parseInt(split[4]);
tTid += tid;
ids[i] = new Task(id, act, tid, staff);
j = 4;
/*
* Lesingen av inputen skal avbrytes når den leser 0.
* j er den som holder på hvor langt vi er i split arrayet
* når den møter på 0
*/
while(split[j].compareTo("0") != 0) {
int tmp = Integer.parseInt(split[j])-1;
// System.out.println(tmp+1 + " Aktivitetens navn : " + act); //+ " tiden aktiviteten tar tid: " + tid + " avhengihet: " + split[j]);
j++;
if (ids[tmp] == null) {
ids[tmp] = new Task(id, act, tid, staff);
ids[tmp].visited = true;
}
ids[i].cntPredecessors++;
if(ids[tmp].outEdge == null) {
ids[tmp].outEdge = new Edge(ids[tmp], ids[i]);
} else {
til = ids[tmp].outEdge;
while(til.neste != null) {
til = til.neste;
}
// til.neste = new Edge(ids[tmp], ids[i]);
}
}
counter++;
i++;
}
if (antTask == counter) {
System.out.println("Lesinga gikk som planlagt av fil: " + fil);
System.out.println("Total arbeidstid: " + tTid);// + antTask + " == " + counter );
} else {
System.out.println("Noe gikk galt avslutter!");
System.out.println(antTask + " || " + counter);
System.exit(2);
}
in.close();
} catch (Exception e) {
System.err.println("Dette gikk galt med lesinga: " + e.getMessage());
}
}
static void topSort() {
LinkedList<Task> list = new LinkedList<Task>();
ArrayList<Task> array = new ArrayList<Task>();
Task temp;
int totalTime = 0;
int counter = 0;
for(Task t : ids) {
if (t.cntPredecessors == 0) {
list.add(t);
}
}
while (!list.isEmpty()) {
temp = list.pop();
counter++;
array.add(temp);
System.out.println("Time " + totalTime + "\t Started task " + temp.id + "\t Staff: " + temp.staff + ", Task done " + temp.id);
totalTime += temp.time;
for (Task t : ids) {
if (--t.cntPredecessors == 0)
list.add(t);
}
}
if(counter < antTask) { // checking for loop
System.out.println(counter + " != " + antTask);
System.out.println("En løkke er funnet i grafen. Avslutter...");
System.exit(0);
}
System.out.println("Topological sort: " + Arrays.toString(array.toArray()));// den sorterte "arraylisten"
System.out.println("Total tid brukt er: " + totalTime);
}
}
class Task {
int id, time, staff;
int depA, depB;
String name;
int eStart, lStart;
Edge outEdge;
int cntPredecessors;
boolean visited;
Task(int id, String name, int time, int staff) {
this.id = id;
this.name = name;
this.time = time;
this.staff = staff;
visited = false;
}
public String getName() {
return name;
}
public String toString() {
return name;
}
}
class Edge {
Task fra, til;
Task id, name, time, staff;
Edge neste;
// Task fra, til;
Edge(Task fra, Task til) { //, Task fra, Task til) {//, Task name, Task time, Task staff) {
this.fra = fra;
this.til = til;
// this.id = id;
// this.fra = fra;
// this.til = til;
/* this.name = name;
this.time = time;
this.staff = staff;*/
}
public Task getTil() {
return til;
}
}
最佳答案
我会在这里写一些简单的算法,你正在做的是拓扑排序
重要的是拓扑排序使用的是 DFS 算法 O(V+E)
您应该做的是为每个节点创建某种附加属性(我们将其称为字符串颜色
并将其初始值设置为白色。
当您将迭代节点时,将其颜色设置为灰色,并继续执行 DFS,完成后将其颜色设置为黑色。
重点是 - 如果您访问 color == grey
或 color == black
的节点,您就发现了一个循环
我建议阅读Topological sort chapter来自Introduction to Algorithms
让我们看看你的代码!
您从输入文件中读取了一些内容,重要部分在这里:
while (!list.isEmpty()) {
temp = list.pop();
counter++;
array.add(temp);
System.out.println("Time " + totalTime + "\t Started task " + temp.id + "\t Staff: " + temp.staff + ", Task done " + temp.id);
totalTime += temp.time;
for (Task t : ids) {
if (--t.cntPredecessors == 0) {
list.add(t);
}
}
}
很抱歉这样说,但是你的代码有点困惑,没有英文文档等。但我认为你错过了为节点着色的部分,这可能是你找不到循环的原因(我想你永远不会结束),因为你错过了为你的节点“着色”,所以没有人知道你已经访问过它们
顺便说一句,我的“颜色”属性在您的代码中被称为“visited”(您可以使用 boolean 值,但不能像我在此处发布的书中那样将其着色为灰/黑/白)
我猜你在初始化期间将其设置为true(你应该将其设置为false,如果你已经处理/访问了该节点,则将其设置为true)
//抱歉,如果我错了,现在是凌晨 1 点。在这里,我只是认为这可能是问题所在
//+ 如果您在有向图上执行此操作,并在检测到循环时退出,您将在 O(V) 时间内获得循环检测算法:)
关于java - 拓扑排序和循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8290031/