Я успешно реализовал алгоритм топологической сортировки, но у меня возникли проблемы с определением, когда вызывать исключение, если введенный граф не ациклический. Есть ли в алгоритме способ проверить это с помощью внутренней степени? Или что-то еще в этом отношении?
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;
}