Рубрики

Обнаружение цикла в неориентированном графике

,
Учитывая неориентированный граф, как проверить, есть ли цикл в графе? Например, следующий график имеет цикл 1-0-2-1.

Мы обсудили обнаружение цикла для ориентированного графа . Мы также обсудили алгоритм поиска объединения для обнаружения цикла в неориентированных графах. Временная сложность алгоритма поиска объединения составляет O (ELogV). Как и ориентированные графы, мы можем использовать DFS для обнаружения цикла в неориентированном графе за время O (V + E). Мы делаем DFS обход данного графа. Для каждой посещенной вершины v, если есть соседняя u, такая, что u уже посещена, и u не является родителем v, то в графе есть цикл. Если мы не найдем такого смежного для какой-либо вершины, мы говорим, что цикла нет. Предположение этого подхода состоит в том, что между любыми двумя вершинами нет параллельных ребер.

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

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

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[], int parent);

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.

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

}

  
// Рекурсивная функция, которая использует visit [] и parent для обнаружения
// цикл в подграфе, достижимом из вершины v.

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

{

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

    visited[v] = true;

  

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

    list<int>::iterator i;

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

    {

        // Если соседний не посещен, то повторяем для этого соседнего

        if (!visited[*i])

        {

           if (isCyclicUtil(*i, visited, v))

              return true;

        }

  

        // Если соседний посещен и не является родителем текущей вершины,

        // тогда есть цикл.

        else if (*i != parent)

           return true;

    }

    return false;

}

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

bool Graph::isCyclic()

{

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

    // стек

    bool *visited = new bool[V];

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

        visited[i] = false;

  

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

    // деревья DFS

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

        if (!visited[u]) // Не повторяться для вас, если он уже посещен

          if (isCyclicUtil(u, visited, -1))

             return true;

  

    return false;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    Graph g1(5);

    g1.addEdge(1, 0);

    g1.addEdge(0, 2);

    g1.addEdge(2, 1);

    g1.addEdge(0, 3);

    g1.addEdge(3, 4);

    g1.isCyclic()? cout << "Graph contains cycle\n":

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

  

    Graph g2(3);

    g2.addEdge(0, 1);

    g2.addEdge(1, 2);

    g2.isCyclic()? cout << "Graph contains cycle\n":

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

  

    return 0;

}

Джава

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

import java.io.*;

import java.util.*;

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

class Graph

{

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

    private LinkedList<Integer> adj[]; // Пересмотр списка смежности

  

    // Конструктор

    Graph(int v) {

        V = v;

        adj = new LinkedList[v];

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

            adj[i] = new LinkedList();

    }

  

    // Функция для добавления ребра в график

    void addEdge(int v,int w) {

        adj[v].add(w);

        adj[w].add(v);

    }

  

    // Рекурсивная функция, которая использует visit [] и parent для обнаружения

    // цикл в подграфе, достижимом из вершины v.

    Boolean isCyclicUtil(int v, Boolean visited[], int parent)

    {

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

        visited[v] = true;

        Integer i;

  

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

        Iterator<Integer> it = adj[v].iterator();

        while (it.hasNext())

        {

            i = it.next();

  

            // Если соседний не посещен, то повторить для этого

            // смежный

            if (!visited[i])

            {

                if (isCyclicUtil(i, visited, v))

                    return true;

            }

  

            // Если соседний посещен и не является родителем текущего

            // вершина, то есть цикл.

            else if (i != parent)

                return true;

        }

        return false;

    }

  

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

    Boolean isCyclic()

    {

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

        // стек рекурсии

        Boolean visited[] = new Boolean[V];

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

            visited[i] = false;

  

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

        // разные деревья DFS

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

            if (!visited[u]) // Не повторяться, если вы уже посетили

                if (isCyclicUtil(u, visited, -1))

                    return true;

  

        return false;

    }

  

  

    // Метод драйвера для тестирования вышеуказанных методов

    public static void main(String args[])

    {

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

        Graph g1 = new Graph(5);

        g1.addEdge(1, 0);

        g1.addEdge(0, 2);

        g1.addEdge(2, 1);

        g1.addEdge(0, 3);

        g1.addEdge(3, 4);

        if (g1.isCyclic())

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

        else

            System.out.println("Graph doesn't contains cycle");

  

        Graph g2 = new Graph(3);

        g2.addEdge(0, 1);

        g2.addEdge(1, 2);

        if (g2.isCyclic())

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

        else

            System.out.println("Graph doesn't contains cycle");

    }

}
// Этот код предоставлен Aakash Hasija

питон

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

  

from collections import defaultdict

   
# Этот класс представляет неориентированный граф, используя представление списка смежности

class Graph:

   

    def __init__(self,vertices):

        self.V= vertices #No. вершин

        self.graph = defaultdict(list) # словарь по умолчанию для хранения графика

  

   

    # функция для добавления ребра на график

    def addEdge(self,v,w):

        self.graph[v].append(w) # Добавить w к списку v_s

        self.graph[w].append(v) # Добавить v в список w_s

   

    # Рекурсивная функция, которая использует посещенный [] и родительский для обнаружения

    # цикл в подграфе, достижимый из вершины v.

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

  

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

        visited[v]= True

  

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

        for i in self.graph[v]:

            # Если узел не посещен, рекурсировать на нем

            if  visited[i]==False

                if(self.isCyclicUtil(i,visited,v)):

                    return True

            # Если соседняя вершина посещена и не является родителем текущей вершины,

            # тогда есть цикл

            elif  parent!=i:

                return True

          

        return False

           

   

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

    def isCyclic(self):

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

        visited =[False]*(self.V)

        # Вызовите рекурсивную вспомогательную функцию, чтобы обнаружить цикл в разных

        #DFS деревья

        for i in range(self.V):

            if visited[i] ==False: # Не повторяться, если он уже посещен

                if(self.isCyclicUtil(i,visited,-1))== True:

                    return True

          

        return False

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

g = Graph(5)

g.addEdge(1, 0)

g.addEdge(0, 2)

g.addEdge(2, 0)

g.addEdge(0, 3)

g.addEdge(3, 4)

  

if g.isCyclic():

    print "Graph contains cycle"

else :

    print "Graph does not contain cycle "

g1 = Graph(3)

g1.addEdge(0,1)

g1.addEdge(1,2)

  

  

if g1.isCyclic():

    print "Graph contains cycle"

else :

    print "Graph does not contain cycle "

   
# Этот код предоставлен Ниламом Ядавом

C #

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

using System;

using System.Collections.Generic;

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

class Graph

{

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

      

    // Пересмотр списка смежности

    private List<int> []adj; 

  

    // Конструктор

    Graph(int v) 

    {

        V = v;

        adj = new List<int>[v];

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

            adj[i] = new List<int>();

    }

  

    // Функция для добавления ребра в график

    void addEdge(int v, int w) 

    {

        adj[v].Add(w);

        adj[w].Add(v);

    }

  

    // Рекурсивная функция, которая использует с посещением []

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

    // достижимы из вершины v.

    Boolean isCyclicUtil(int v, Boolean []visited,

                         int parent)

    {

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

        visited[v] = true;

  

        // повторить для всех вершин

        // рядом с этой вершиной

        foreach(int i in adj[v])

        {

            // Если соседний не посещен,

            // затем повторяем для этого смежного

            if (!visited[i])

            {

                if (isCyclicUtil(i, visited, v))

                    return true;

            }

  

            // Если соседний посещен и

            // не является родителем текущей вершины,

            // тогда есть цикл.

            else if (i != parent)

                return true;

        }

        return false;

    }

  

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

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

    Boolean isCyclic()

    {

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

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

        Boolean []visited = new Boolean[V];

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

            visited[i] = false;

  

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

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

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

          

            // Не повторяться, если вы уже посетили

            if (!visited[u]) 

                if (isCyclicUtil(u, visited, -1))

                    return true;

  

        return false;

    }

  

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

    public static void Main(String []args)

    {

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

        Graph g1 = new Graph(5);

        g1.addEdge(1, 0);

        g1.addEdge(0, 2);

        g1.addEdge(2, 1);

        g1.addEdge(0, 3);

        g1.addEdge(3, 4);

        if (g1.isCyclic())

            Console.WriteLine("Graph contains cycle");

        else

            Console.WriteLine("Graph doesn't contains cycle");

  

        Graph g2 = new Graph(3);

        g2.addEdge(0, 1);

        g2.addEdge(1, 2);

        if (g2.isCyclic())

            Console.WriteLine("Graph contains cycle");

        else

            Console.WriteLine("Graph doesn't contains cycle");

    }

}

  
// Этот код предоставлен PrinciRaj1992

Выход:

Graph contains cycle
Graph doesn't contain cycle

Сложность времени: программа выполняет простой DFS обход графа и граф представлен в списке смежности. Таким образом, сложность времени O (V + E)

Упражнение: Можем ли мы использовать BFS для обнаружения цикла в неориентированном графе за время O (V + E)? Как насчет ориентированных графов?

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

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

Обнаружение цикла в неориентированном графике

0.00 (0%) 0 votes