Рубрики

Программа C для обнаружения цикла в ориентированном графике

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

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

  

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.

}

  
// Эта функция является разновидностью DFSUytil ()
// в 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;

}

Выход:

Graph contains cycle

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

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

Программа C для обнаружения цикла в ориентированном графике

0.00 (0%) 0 votes