Рубрики

Java-программа для обнаружения цикла в ориентированном графе

По заданному ориентированному графу проверьте, содержит ли граф цикл или нет. Ваша функция должна возвращать true, если данный граф содержит хотя бы один цикл, иначе возвращает false. Например, следующий график содержит три цикла 0-> 2-> 0, 0-> 1-> 2-> 0 и 3-> 3, поэтому ваша функция должна возвращать true.

// Java-программа для определения цикла в графе

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

  

class Graph {

  

    private final int V;

    private final List<List<Integer> > adj;

  

    public Graph(int V)

    {

        this.V = V;

        adj = new ArrayList<>(V);

  

        for (int i = 0; i < V; i++)

            adj.add(new LinkedList<>());

    }

  

    // Эта функция является разновидностью DFSUytil () в

    // https: // www.geeksforgeeks.org/archives/18212

    private boolean isCyclicUtil(int i, boolean[] visited,

                                 boolean[] recStack)

    {

  

        // Пометить текущий узел как посещенный и

        // часть стека рекурсии

        if (recStack[i])

            return true;

  

        if (visited[i])

            return false;

  

        visited[i] = true;

  

        recStack[i] = true;

        List<Integer> children = adj.get(i);

  

        for (Integer c : children)

            if (isCyclicUtil(c, visited, recStack))

                return true;

  

        recStack[i] = false;

  

        return false;

    }

  

    private void addEdge(int source, int dest)

    {

        adj.get(source).add(dest);

    }

  

    // Возвращает true, если график содержит

    // цикл, иначе ложь.

    // Эта функция является разновидностью DFS () в

    // https: // www.geeksforgeeks.org/archives/18212

    private boolean isCyclic()

    {

  

        // Пометить все вершины как не посещенные и

        // не является частью стека рекурсии

        boolean[] visited = new boolean[V];

        boolean[] recStack = new boolean[V];

  

        // Вызов рекурсивной вспомогательной функции для

        // обнаружение цикла в разных деревьях DFS

        for (int i = 0; i < V; i++)

            if (isCyclicUtil(i, visited, recStack))

                return true;

  

        return false;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        Graph graph = new Graph(4);

        graph.addEdge(0, 1);

        graph.addEdge(0, 2);

        graph.addEdge(1, 2);

        graph.addEdge(2, 0);

        graph.addEdge(2, 3);

        graph.addEdge(3, 3);

  

        if (graph.isCyclic())

            System.out.println("Graph contains cycle");

        else

            System.out.println("Graph doesn't "

                               + "contain cycle");

    }

}

  
// Этот код предоставлен Сагар Шахом.

Выход:

Graph contains cycle

Пожалуйста, обратитесь к полной статье об Обнаружении Цикла в Направленном Графе для более подробной информации!

Рекомендуемые посты:

Java-программа для обнаружения цикла в ориентированном графе

0.00 (0%) 0 votes