Автор оригинала: Shubhra Srivastava.
1. Обзор
В этом кратком руководстве мы узнаем, как мы можем обнаружить цикл в заданном ориентированном графе.
2. Графическое представление
В этом уроке мы будем придерживаться представления графа списка смежности .
В этом уроке мы будем придерживаться представления графа списка смежности .
public class Vertex {
private String label;
private boolean beingVisited;
private boolean visited;
private List adjacencyList;
public Vertex(String label) {
this.label = label;
this.adjacencyList = new ArrayList<>();
}
public void addNeighbor(Vertex adjacent) {
this.adjacencyList.add(adjacent);
}
//getters and setters
} Здесь список смежности вершины v содержит список всех вершин, смежных с v . Метод add Neighbor() добавляет соседнюю вершину в список смежности v .
Мы также определили два логических параметра, | посещаемый и посещаемый, которые представляют, посещается ли узел в данный момент или уже посещался.
Граф можно рассматривать как группу вершин или узлов, соединенных ребрами.
Итак, давайте теперь быстро представим График в Java:
public class Graph {
private List vertices;
public Graph() {
this.vertices = new ArrayList<>();
}
public void addVertex(Vertex vertex) {
this.vertices.add(vertex);
}
public void addEdge(Vertex from, Vertex to) {
from.addNeighbor(to);
}
// ...
} Мы будем использовать методы addVertex() и addEdge() для добавления новых вершин и ребер в наш граф.
3. Обнаружение цикла
Чтобы обнаружить цикл в ориентированном графе, мы будем использовать вариант DFS обхода:
- Выберите не посещенную вершину v и отметьте ее состояние как посещаемую
Для каждой соседней вершины u of v, проверьте:
- Если u уже находится в состоянии посещается , это явно означает, что существует обратная граница, и поэтому цикл был обнаружен
- Если u все еще находится в не посещенном состоянии, мы рекурсивно посетим u в первую очередь
- Обновите вершину v ‘s посещаемый флаг на false и ее посещаемый флаг на true
Обратите внимание, что все вершины нашего графа изначально находятся в не посещенном состоянии, так как их посещаемые и посещаемые флаги инициализируются с false .
Давайте теперь рассмотрим наше решение Java:
public boolean hasCycle(Vertex sourceVertex) {
sourceVertex.setBeingVisited(true);
for (Vertex neighbor : sourceVertex.getAdjacencyList()) {
if (neighbor.isBeingVisited()) {
// backward edge exists
return true;
} else if (!neighbor.isVisited() && hasCycle(neighbor)) {
return true;
}
}
sourceVertex.setBeingVisited(false);
sourceVertex.setVisited(true);
return false;
}Мы можем использовать любую вершину в графе в качестве исходной или начальной вершины.
Для несвязанного графика нам придется добавить дополнительный метод обертки:
public boolean hasCycle() {
for (Vertex vertex : vertices) {
if (!vertex.isVisited() && hasCycle(vertex)) {
return true;
}
}
return false;
}Это делается для того, чтобы убедиться, что мы посещаем каждый компонент несвязанного графика для обнаружения цикла.
4. Тестирование реализации
Рассмотрим приведенный ниже циклический ориентированный граф:
Мы можем быстро написать JUnit для проверки нашего метода hasCycle() для этого графика:
@Test
public void givenGraph_whenCycleExists_thenReturnTrue() {
Vertex vertexA = new Vertex("A");
Vertex vertexB = new Vertex("B");
Vertex vertexC = new Vertex("C")
Vertex vertexD = new Vertex("D");
Graph graph = new Graph();
graph.addVertex(vertexA);
graph.addVertex(vertexB);
graph.addVertex(vertexC);
graph.addVertex(vertexD);
graph.addEdge(vertexA, vertexB);
graph.addEdge(vertexB, vertexC);
graph.addEdge(vertexC, vertexA);
graph.addEdge(vertexD, vertexC);
assertTrue(graph.hasCycle());
}Здесь наш имеет метод Cycle () , возвращающий true , обозначающий, что наш граф цикличен.
5. Заключение
В этом уроке мы узнали, как проверить, существует ли цикл в заданном ориентированном графе в Java.
Как обычно, реализация кода с примерами доступна на Github .