java - 拓扑排序和周期

我从老师那里得到了一些输入文件，我们应该以此来测试程序。任务是从文件读取，创建有向图并打印输出。但是，如果有一个周期，我们应该终止程序。

我有一些名为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）

您应该做的是为每个Node创建某种附加属性（我们将其称为String color并将其初始值设置为white。

当您遍历节点时，将其颜色设置为灰色，然后继续执行DFS，完成后，将其颜色设置为黑色。

关键是-如果您访问带有color == gray或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);
                }
            }
        }

很抱歉这样说，但是您的代码有点混乱，没有英文文档，等等。但是我认为您缺少为节点着色的部分，这可能就是您找不到循环的原因（而且我假设您永无止境），因为您错过了为节点“着色”的机会，因此没人知道您已经访问了它们

顺便说一句，我的“颜色”属性在您的代码中被称为“访问”（您可以使用布尔值，但不能像我在此处发布的书中那样将其颜色设置为灰色/黑色/白色）

我猜您在初始化期间将其设置为true（如果已经处理/访问了该节点，则应将其设置为false并将其设置为true）

//对不起，如果我输入错了，那是1A.M.在这里，我只是认为这可能是问题所在

// +如果在有向图上执行此操作，并且在检测到循环时退出，则在O（V）时间中获得并检测循环算法：)

关于java - 拓扑排序和周期，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8290031/