Перейти к основному содержимому

Проверка наличия цикла в Java Graph

· 3 мин. чтения

Задача: Наибольшая подстрока палиндром

Для заданной строки s, верните наибольшую подстроку палиндром входящую в s. Подстрока — это непрерывная непустая последовательность символов внутри строки. Стока является палиндромом, если она читается одинаково в обоих направлениях...

ANDROMEDA 42

1. Обзор

В этом кратком руководстве мы узнаем, как мы можем обнаружить цикл в заданном ориентированном графе.

2. Графическое представление

В этом руководстве мы будем придерживаться графа списка смежности .

Во-первых, давайте начнем с определения вершины в Java:

public class Vertex {

private String label;
private boolean beingVisited;
private boolean visited;
private List<Vertex> adjacencyList;

public Vertex(String label) {
this.label = label;
this.adjacencyList = new ArrayList<>();
}

public void addNeighbor(Vertex adjacent) {
this.adjacencyList.add(adjacent);
}
//getters and setters
}

Здесь adjacencyList вершины v содержит список всех вершин, смежных с v . Метод addNeighbor() добавляет соседнюю вершину в список смежности v .

Мы также определили два логических параметра, посещенных и посещенных, которые показывают, посещается ли узел в настоящее время или уже был посещен.

Граф можно рассматривать как группу вершин или узлов, соединенных ребрами.

Итак, давайте теперь быстро представим Graph в Java:

public class Graph {

private List<Vertex> 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. Обнаружение цикла

Чтобы обнаружить цикл в ориентированном графе, мы будем использовать вариант обхода в глубину:

  • Выберите непосещенную вершину v и отметьте ее состояние как Посещенная.

  • Для каждой соседней вершины u из v проверьте:

  • Если u уже находится в состоянии BeingVisited , это явно означает , что существует обратная граница и, следовательно, обнаружен цикл.

  • Если u все еще находится в состоянии unvisited, мы рекурсивно посетим u в глубине.

  • Обновите флаг bevisited вершины v до значения 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. Тестирование реализации

Рассмотрим приведенный ниже циклический ориентированный граф:

./c6d635e7ac73b3b6321d0eb19954b357.png

Мы можем быстро написать 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());

}

Здесь наш метод hasCycle() вернул true , что означает, что наш график является циклическим.

5. Вывод

В этом уроке мы узнали, как проверить, существует ли цикл в заданном ориентированном графе в Java.

Как обычно, реализация кода с примерами доступна на Github .