java - 确定图形是非循环的还是拓扑排序的

Question

我已经成功地实现了一个拓扑排序算法，但是当输入的图不是无环图时，我无法确定何时抛出异常。在算法中有没有一种方法可以使用入度来检查这一点？还是其他什么？

public static List<String> topologicalSort(Graph graph) {

    if(graph.getDirected() == false)
        throw new UnsupportedOperationException();

    Queue<Vertex> queue = new LinkedList<Vertex>();

    HashMap<String, Vertex> tempMap = graph.getVertices();
    for(Vertex vertex : tempMap.values()) {
        if(vertex.getInDegree() == 0)
            queue.add(vertex);
    }

    if(queue.isEmpty())
        throw new UnsupportedOperationException();

    ArrayList<String> returnList = new ArrayList<String>();
    while(!queue.isEmpty()) {
        Vertex tempVert = queue.poll();
        returnList.add(tempVert.getName());
        tempVert.setVisited(true);
        for(Edge edge : tempVert.getEdges()) {

           if(edge.getOtherVertex().getVisited() == true)
                throw new UnsupportedOperationException();
           edge.getOtherVertex().setVisited(true);
           edge.getOtherVertex().decInDegree();

           if(edge.getOtherVertex().getInDegree() == 0)
               queue.add(edge.getOtherVertex());
        }

    }

    return returnList;
}

Answer 1

如果输入是一个带有循环的图，那么您将到达算法中尚未将所有节点添加到输出的点，但队列中也没有任何其他元素(您可以'因为有循环关系，将循环中的任意一个节点加入到队列中)。

即在 while 循环之后检查 returnList.size() == graph.nodeCount()(true 表示非循环输入，false 表示输入有循环).

graph.nodeCount() 应该是方法开始时图中的节点数。