Рубрики

Разъединенный набор (или союз-поиск) | Установите 1 (обнаружение цикла в неориентированном графике)

Структура данных с несвязным множеством — это структура данных, которая отслеживает набор элементов, разделенных на несколько непересекающихся (не перекрывающихся) подмножеств. Алгоритм поиска объединения — это алгоритм, который выполняет две полезные операции с такой структурой данных:

Найти: определить, в каком подмножестве находится конкретный элемент. Это можно использовать для определения того, находятся ли два элемента в одном подмножестве.

Объединение: объединить два подмножества в одно подмножество.

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

Алгоритм Union-Find можно использовать для проверки того, содержит ли ненаправленный граф цикл или нет. Обратите внимание, что мы обсудили алгоритм обнаружения цикла . Это еще один метод, основанный на Union-Find . Этот метод предполагает, что граф не содержит никаких циклов.
Мы можем отслеживать подмножества в одномерном массиве, назовем его parent [].

Давайте рассмотрим следующий график:

Для каждого ребра создайте подмножества, используя обе вершины ребра. Если обе вершины находятся в одном и том же подмножестве, цикл найден.

Первоначально все слоты родительского массива инициализируются в -1 (означает, что в каждом подмножестве только один элемент).

0   1   2
-1 -1  -1 

Теперь обработайте все ребра по одному.

Край 0-1: Найдите подмножества, в которых находятся вершины 0 и 1. Поскольку они находятся в разных подмножествах, мы берем их объединение. Для принятия объединения либо сделайте узел 0 родительским для узла 1, либо наоборот.

0   1   2    <----- 1 is made parent of 0 (1 is now representative of subset {0, 1})
1  -1  -1

Край 1-2: 1 находится в подмножестве 1, а 2 — в подмножестве 2. Итак, возьмем объединение.

0   1   2    <----- 2 is made parent of 1 (2 is now representative of subset {0, 1, 2})
1   2  -1

Ребро 0-2: 0 находится в подмножестве 2, а 2 также в подмножестве 2. Следовательно, включение этого ребра образует цикл.

Как подмножество 0 совпадает с 2?
0-> 1-> 2 // 1 является родителем 0, а 2 является родителем 1

На основании вышеприведенного объяснения ниже приведены реализации:

C ++

// Алгоритм поиска объединения для обнаружения цикла в графе
#include <bits/stdc++.h>

using namespace std;

  
// структура для представления ребра в графе

class Edge 

    public:

    int src, dest; 

}; 

  
// структура для представления графика

class Graph 

    public:

    // V-> Количество вершин, E-> Количество ребер

    int V, E; 

  

    // график представлен в виде массива ребер

    Edge* edge; 

}; 

  
// Создаем граф с V вершинами и E ребрами

Graph* createGraph(int V, int E) 

    Graph* graph = new Graph();

    graph->V = V; 

    graph->E = E; 

  

    graph->edge = new Edge[graph->E * sizeof(Edge)]; 

  

    return graph; 

  
// Полезная функция для поиска подмножества элемента i

int find(int parent[], int i) 

    if (parent[i] == -1) 

        return i; 

    return find(parent, parent[i]); 

  
// Полезная функция для объединения двух подмножеств

void Union(int parent[], int x, int y) 

    int xset = find(parent, x); 

    int yset = find(parent, y); 

    if(xset != yset)

    

        parent[xset] = yset; 

    

  
// Основная функция, чтобы проверить, содержит ли данный граф
// цикл или нет

int isCycle( Graph* graph ) 

    // Выделим память для создания V подмножеств

    int *parent = new int[graph->V * sizeof(int)]; 

  

    // Инициализируем все подмножества как наборы из одного элемента

    memset(parent, -1, sizeof(int) * graph->V); 

  

    // Перебирать все ребра графа, найти подмножество обоих

    // вершины каждого ребра, если оба подмножества одинаковы, то

    // в графе есть цикл

    for(int i = 0; i < graph->E; ++i) 

    

        int x = find(parent, graph->edge[i].src); 

        int y = find(parent, graph->edge[i].dest); 

  

        if (x == y) 

            return 1; 

  

        Union(parent, x, y); 

    

    return 0; 

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

int main() 

    / * Давайте создадим следующий график

        0

        | /

        | /

        1 ----- 2 * /

    int V = 3, E = 3; 

    Graph* graph = createGraph(V, E); 

  

    // добавляем ребро 0-1

    graph->edge[0].src = 0; 

    graph->edge[0].dest = 1; 

  

    // добавить ребро 1-2

    graph->edge[1].src = 1; 

    graph->edge[1].dest = 2; 

  

    // добавляем ребро 0-2

    graph->edge[2].src = 0; 

    graph->edge[2].dest = 2; 

  

    if (isCycle(graph)) 

        cout<<"graph contains cycle"

    else

        cout<<"graph doesn't contain cycle"

  

    return 0; 

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

С

// Алгоритм поиска объединения для обнаружения цикла в графе
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

  
// структура для представления ребра в графе

struct Edge

{

    int src, dest;

};

  
// структура для представления графика

struct Graph

{

    // V-> Количество вершин, E-> Количество ребер

    int V, E;

  

    // график представлен в виде массива ребер

    struct Edge* edge;

};

  
// Создаем граф с V вершинами и E ребрами

struct Graph* createGraph(int V, int E)

{

    struct Graph* graph = 

           (struct Graph*) malloc( sizeof(struct Graph) );

    graph->V = V;

    graph->E = E;

  

    graph->edge = 

        (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

  

    return graph;

}

  
// Полезная функция для поиска подмножества элемента i

int find(int parent[], int i)

{

    if (parent[i] == -1)

        return i;

    return find(parent, parent[i]);

}

  
// Полезная функция для объединения двух подмножеств

void Union(int parent[], int x, int y)

{

    int xset = find(parent, x);

    int yset = find(parent, y);

    if(xset!=yset){

       parent[xset] = yset;

    }

}

  
// Основная функция, чтобы проверить, содержит ли данный граф
// цикл или нет

int isCycle( struct Graph* graph )

{

    // Выделим память для создания V подмножеств

    int *parent = (int*) malloc( graph->V * sizeof(int) );

  

    // Инициализируем все подмножества как наборы из одного элемента

    memset(parent, -1, sizeof(int) * graph->V);

  

    // Перебирать все ребра графа, найти подмножество обоих

    // вершины каждого ребра, если оба подмножества одинаковы, то

    // в графе есть цикл

    for(int i = 0; i < graph->E; ++i)

    {

        int x = find(parent, graph->edge[i].src);

        int y = find(parent, graph->edge[i].dest);

  

        if (x == y)

            return 1;

  

        Union(parent, x, y);

    }

    return 0;

}

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

int main()

{

    / * Давайте создадим следующий график

         0

        | /

        | /

        1 ----- 2 * /     

    int V = 3, E = 3;

    struct Graph* graph = createGraph(V, E);

  

    // добавляем ребро 0-1

    graph->edge[0].src = 0;

    graph->edge[0].dest = 1;

  

    // добавить ребро 1-2

    graph->edge[1].src = 1;

    graph->edge[1].dest = 2;

  

    // добавляем ребро 0-2

    graph->edge[2].src = 0;

    graph->edge[2].dest = 2;

  

    if (isCycle(graph))

        printf( "graph contains cycle" );

    else

        printf( "graph doesn't contain cycle" );

  

    return 0;

}

Джава

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

import java.util.*;

import java.lang.*;

import java.io.*;

  

class Graph

{

    int V, E;    // V-> нет. вершин и E-> количество ребер

    Edge edge[]; // / коллекция всех ребер

  

    class Edge

    {

        int src, dest;

    };

  

    // Создаем граф с V вершинами и E ребрами

    Graph(int v,int e)

    {

        V = v;

        E = e;

        edge = new Edge[E];

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

            edge[i] = new Edge();

    }

  

    // Полезная функция для поиска подмножества элемента i

    int find(int parent[], int i)

    {

        if (parent[i] == -1)

            return i;

        return find(parent, parent[i]);

    }

  

    // Полезная функция для объединения двух подмножеств

    void Union(int parent[], int x, int y)

    {

        int xset = find(parent, x);

        int yset = find(parent, y);

        parent[xset] = yset;

    }

  

  

    // Основная функция, чтобы проверить, является ли данный граф

    // содержит цикл или нет

    int isCycle( Graph graph)

    {

        // Выделим память для создания V подмножеств

        int parent[] = new int[graph.V];

  

        // Инициализируем все подмножества как наборы из одного элемента

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

            parent[i]=-1;

  

        // Перебирать все ребра графа, найти подмножество обоих

        // вершины каждого ребра, если оба подмножества одинаковы, то

        // в графе есть цикл

        for (int i = 0; i < graph.E; ++i)

        {

            int x = graph.find(parent, graph.edge[i].src);

            int y = graph.find(parent, graph.edge[i].dest);

  

            if (x == y)

                return 1;

  

            graph.Union(parent, x, y);

        }

        return 0;

    }

  

    // Метод драйвера

    public static void main (String[] args)

    {

        / * Давайте создадим следующий график

         0

        | /

        | /

        1 ----- 2 * /

        int V = 3, E = 3;

        Graph graph = new Graph(V, E);

  

        // добавляем ребро 0-1

        graph.edge[0].src = 0;

        graph.edge[0].dest = 1;

  

        // добавить ребро 1-2

        graph.edge[1].src = 1;

        graph.edge[1].dest = 2;

  

        // добавляем ребро 0-2

        graph.edge[2].src = 0;

        graph.edge[2].dest = 2;

  

        if (graph.isCycle(graph)==1)

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

        else

            System.out.println( "graph doesn't contain cycle" );

    }

}

питон

# Программа Python для алгоритма union-find для обнаружения цикла в неориентированном графе
# у нас есть один egde для любых двух вершин, то есть 1-2 это либо 1-2, либо 2-1, но не оба

   

from collections import defaultdict

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

class Graph:

   

    def __init__(self,vertices):

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

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

   

  

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

    def addEdge(self,u,v):

        self.graph[u].append(v)

   

    # Полезная функция для поиска подмножества элемента i

    def find_parent(self, parent,i):

        if parent[i] == -1:

            return i

        if parent[i]!= -1:

             return self.find_parent(parent,parent[i])

  

    # Полезная функция для объединения двух подмножеств

    def union(self,parent,x,y):

        x_set = self.find_parent(parent, x)

        y_set = self.find_parent(parent, y)

        parent[x_set] = y_set

  

   

   

    # Основная функция, чтобы проверить, является ли данный граф

    # содержит цикл или нет

    def isCyclic(self):

          

        # Выделите память для создания V подмножеств и

        # Инициализировать все подмножества как наборы из одного элемента

        parent = [-1]*(self.V)

  

        # Перебрать все ребра графа, найти подмножество обоих

        # вершин каждого ребра, если оба подмножества одинаковы, то

        # есть цикл в графе.

        for i in self.graph:

            for j in self.graph[i]:

                x = self.find_parent(parent, i) 

                y = self.find_parent(parent, j)

                if x == y:

                    return True

                self.union(parent,x,y)

  

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

g = Graph(3)

g.addEdge(0, 1)

g.addEdge(1, 2)

g.addEdge(2, 0)

  

if g.isCyclic():

    print "Graph contains cycle"

else :

    print "Graph does not contain cycle "

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


Выход:

graph contains cycle

Обратите внимание, что реализация union () и find () наивна и в худшем случае занимает время O (n). Эти методы могут быть улучшены до O (Logn) с помощью объединения по рангу или высоте . Мы скоро будем обсуждать Союз по рангу в отдельном посте.

Статьи по Теме :
Союз-Найти Алгоритм | Набор 2 (объединение по рангу и сжатию пути)
Несвязанные структуры данных множества (реализация Java)
Жадные алгоритмы | Набор 2 (алгоритм минимального связующего дерева Крускала)
Проблема последовательности работы | Набор 2 (Использование несвязанного набора)

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

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

Разъединенный набор (или союз-поиск) | Установите 1 (обнаружение цикла в неориентированном графике)

0.00 (0%) 0 votes