Рубрики

Определить цикл в ориентированном графике

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

Depth First Traversal может использоваться для обнаружения цикла на графике. DFS для связного графа создает дерево. Цикл в графе существует, только если в графе присутствует задний край . Задний край — это край от узла к себе (самоконтроль) или один из его предков в дереве, создаваемом DFS. На следующем графике есть 3 задних края, помеченных крестиком. Мы можем наблюдать, что эти 3 задних ребра указывают на 3 цикла, присутствующих на графике.

Для отключенного графа мы получаем лес DFS в качестве вывода. Чтобы обнаружить цикл, мы можем проверить цикл в отдельных деревьях, проверив обратные края.

Чтобы обнаружить задний фронт, мы можем отслеживать вершины, в настоящее время находящиеся в стеке рекурсии, для обхода DFS. Если мы достигнем вершины, которая уже находится в стеке рекурсии, то в дереве будет цикл. Ребро, которое соединяет текущую вершину с вершиной в стеке рекурсии, является задним ребром. Мы использовали массив recStack [] для отслеживания вершин в стеке рекурсии.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа на C ++ для определения цикла в графе
#include<iostream>
#include <list>
#include <limits.h>

  

using namespace std;

  

class Graph

{

    int V;    // Количество вершин

    list<int> *adj;    // Указатель на массив, содержащий списки смежности

    bool isCyclicUtil(int v, bool visited[], bool *rs);  // используется isCyclic ()

public:

    Graph(int V);   // Конструктор

    void addEdge(int v, int w);   // добавить ребро на график

    bool isCyclic();    // возвращает true, если в этом графике есть цикл

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

}

  
// Эта функция является разновидностью DFSUtil () в https://www.geeksforgeeks.org/archives/18212

bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)

{

    if(visited[v] == false)

    {

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

        visited[v] = true;

        recStack[v] = true;

  

        // Повторение для всех вершин, смежных с этой вершиной

        list<int>::iterator i;

        for(i = adj[v].begin(); i != adj[v].end(); ++i)

        {

            if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )

                return true;

            else if (recStack[*i])

                return true;

        }

  

    }

    recStack[v] = false// удаляем вершину из стека рекурсии

    return false;

}

  
// Возвращает true, если граф содержит цикл, иначе false.
// Эта функция является разновидностью DFS () в https://www.geeksforgeeks.org/archives/18212

bool Graph::isCyclic()

{

    // Пометить все вершины как не посещенные и не являющиеся частью рекурсии

    // стек

    bool *visited = new bool[V];

    bool *recStack = new bool[V];

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

    {

        visited[i] = false;

        recStack[i] = false;

    }

  

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

    // деревья DFS

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

        if (isCyclicUtil(i, visited, recStack))

            return true;

  

    return false;

}

  

int main()

{

    // Создать график, приведенный на диаграмме выше

    Graph g(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 0);

    g.addEdge(2, 3);

    g.addEdge(3, 3);

  

    if(g.isCyclic())

        cout << "Graph contains cycle";

    else

        cout << "Graph doesn't contain cycle";

    return 0;

}

Джава

// 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");

    }

}

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

питон

# Python программа для определения цикла
# на графике

  

from collections import defaultdict

  

class Graph():

    def __init__(self,vertices):

        self.graph = defaultdict(list)

        self.V = vertices

  

    def addEdge(self,u,v):

        self.graph[u].append(v)

  

    def isCyclicUtil(self, v, visited, recStack):

  

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

        # добавляет в стек рекурсии

        visited[v] = True

        recStack[v] = True

  

        # Повтор для всех соседей

        # если любой сосед посещен и в

        # recStack, то график циклический

        for neighbour in self.graph[v]:

            if visited[neighbour] == False:

                if self.isCyclicUtil(neighbour, visited, recStack) == True:

                    return True

            elif recStack[neighbour] == True:

                return True

  

        # Узел должен быть извлечен из

        # стек рекурсии до завершения функции

        recStack[v] = False

        return False

  

    # Возвращает true, если график циклический, иначе false

    def isCyclic(self):

        visited = [False] * self.V

        recStack = [False] * self.V

        for node in range(self.V):

            if visited[node] == False:

                if self.isCyclicUtil(node,visited,recStack) == True:

                    return True

        return False

  

g = Graph(4)

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

if g.isCyclic() == 1:

    print "Graph has a cycle"

else:

    print "Graph has no cycle"

  
# Спасибо Divyanshu Mehta за предоставленный код


Выход:

Graph contains cycle

Временная сложность этого метода такая же, как временная сложность обхода DFS, которая равна O (V + E).

В статье ниже обсуждается другой метод O (V + E):
Обнаружение цикла в прямом графике с использованием цветов

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Определить цикл в ориентированном графике

0.00 (0%) 0 votes