java找出循环依赖项的路径

Question

我不知道如何打印出循环依赖（循环）存在的路径。如果循环存在，就是这样。我正在对一个包含不同顶点（任务）的图（代表一个项目）进行拓扑排序。有没有一种简单的方法可以做到这一点，或者像深度优先搜索这样的另一种算法更好

以下是我目前掌握的情况：

public boolean canProjectBeCompleted() { 

    if(this.getProjectTasks() == null) {
        return false;
    }

    LinkedList<Task> queue = new LinkedList<Task>();
    Task task;
    int counter = 0;

    Iterator<Task> taskIterator = this.getProjectTasks().values().iterator();
    while(taskIterator.hasNext()) {
        Task t = taskIterator.next();
        if(t.getInEdgesPredecessors().size() == 0) {
            queue.add(t);
        }
    }

    while(!queue.isEmpty()) {
        task = queue.removeFirst();
        counter++;
        for(int i = 0; i < task.getOutEdgesSuccesors().size(); i++) {
            Task neighbour = task.getOutEdgesSuccesors().get(i);
            neighbour.setCopyNumberOfIncomingEdges(neighbour.getCopyNumberOfIncomingEdges()-1);
            if(neighbour.getCopyNumberOfIncomingEdges() == 0) {
                queue.add(neighbour);
            }
        }
    }
    if(counter < amountOfTasks) {
        return false; //Cycle found, The topological sort cannot complete
    }
    return true; //No cycle found
}

提前感谢！：）

Answer 1

这个怎么样

你知道，作为循环的一部分的顶点必须既有向外的边，也有向内的边。所以，像拓扑排序一样开始，用0“移除”（或简单地标记）顶点，并移除其向外的边。转到它的邻居，删除每个现在有0条边的，然后继续。如果图中仍有剩余顶点，则知道剩余顶点中的某个地方有一个循环，但不知道在何处或有多少个循环。这是一种反向拓扑排序，从这里开始移除边为0的顶点。这是因为您知道，没有外出边的顶点不可能是循环的一部分。继续拓扑排序，即删除顶点的边，并对相邻顶点重复。留在图形中的那些顶点是一个或多个循环的一部分。要找出循环的数量和顶点在每个循环中出现的顺序，可以在剩余的图形中执行深度优先搜索

如果我没有弄错的话，我认为复杂性应该是O(|V| + |E|)

Answer 2

图形的邻接矩阵A将为您提供所需的信息， 见http://en.wikipedia.org/wiki/Adjacency_matrix

例如，如果矩阵A到幂p的对角线上的条目为0， 那么就没有长度p的循环。 所以，如果你能使用快速矩阵乘法，那么这可能是最容易实现的

Answer 3

图中有一个简单的循环测试： 连续树（无圈图）包含至少（节点-1）个EGE

这将在无向图中检测循环的存在，并在有向图中复制路径

要检测循环的存在，请先遍历图的宽度（正如您已经做的那样），并在节点出现时将其存储在哈希集中。如果节点已经包含在此集合中，则会有一个循环，您可以立即停止搜索。哈希集的另一种选择是在节点本身上设置一个标志（但这会导致搜索过程不是线程安全的，可能需要修改对象，或者在运行时附加某些方面）

正如我在代码中看到的，您正在修改CopyNumberOfIncomingEdge，而没有检查值 第一你在哪里建的这个房子