Как определить, является ли ориентированный граф циклическим?
Многие объяснения уже присутствуют, чтобы объяснить, как это происходит и как это исправить, но вы также должны следовать рекомендациям, чтобы избежать NullPointerException вообще.
См. также: A хороший список лучших практик
Я бы добавил, очень важно, хорошо использовать модификатор final. Использование "окончательной" модификатор, когда это применимо в Java
Сводка:
- Используйте модификатор
finalдля обеспечения хорошей инициализации. - Избегайте возврата null в методы, например, при возврате пустых коллекций.
- Использовать аннотации
@NotNullи@Nullable - Быстрое завершение работы и использование утверждений, чтобы избежать распространения нулевых объектов через все приложение, когда они не должен быть пустым.
- Сначала используйте значения с известным объектом:
if("knownObject".equals(unknownObject) - Предпочитают
valueOf()поверх toString (). - Используйте null safe
StringUtilsStringUtils.isEmpty(null).
5 ответов
Обычно вместо этого используется поиск глубины. Я не знаю, легко ли применим BFS.
В DFS связующее дерево строится в порядке посещения. Если посещается предок узла в дереве (т.е. создается задний край), то мы обнаруживаем цикл.
Более подробное объяснение см. в http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf.
Тестирование на топологическую сортировку по заданному графику приведет вас к решению. Если алгоритм topsort, то есть ребра всегда должны быть направлены в одну сторону, не работает, то это означает, что граф содержит циклы.
Используйте DFS для поиска, если какой-либо путь является циклическим
class Node<T> { T value; List<Node<T>> adjacent; }
class Graph<T>{
List<Node<T>> nodes;
public boolean isCyclicRec()
{
for (Node<T> node : nodes)
{
Set<Node<T>> initPath = new HashSet<>();
if (isCyclicRec(node, initPath))
{
return true;
}
}
return false;
}
private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path)
{
if (path.contains(currNode))
{
return true;
}
else
{
path.add(currNode);
for (Node<T> node : currNode.adjacent)
{
if (isCyclicRec(node, path))
{
return true;
}
else
{
path.remove(node);
}
}
}
return false;
}
Еще одно простое решение - это метод отметки и развертки. По сути, для каждого узла в дереве вы помечаете его как «посещенный», а затем переходите к его дочерним элементам. Если вы когда-нибудь увидите узел с установленным флагом «visted», вы знаете, что существует цикл.
Если изменение графа для включения «посещенного» бита невозможно, вместо него можно использовать набор указателей узлов. Чтобы пометить узел как посещенный, вы помещаете на него указатель в наборе. Если указатель уже находится в наборе, есть цикл.
Я считаю, что вам действительно нужен алгоритм топологической сортировки, подобный описанному здесь:
http://en.wikipedia.org/wiki/Topological_sorting
Если ориентированный граф имеет цикл, то алгоритм не сработает.
В комментариях / ответах, которые я видел до сих пор, похоже, упускается тот факт, что в направленном графе может быть более одного способа перейти от узла X к узлу Y без каких-либо (направленные) циклы в графе.