Рубрики

Союз-Найти Алгоритм | Набор 2 (объединение по рангу и сжатию пути)

В предыдущем посте мы ввели алгоритм поиска объединения и использовали его для обнаружения цикла в графе. Мы использовали следующие операции union () и find () для подмножеств.

// Наивная реализация find

int find(int parent[], int i)

{

    if (parent[i] == -1)

        return i;

    return find(parent, parent[i]);

}

   
// Наивная реализация union ()

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

{

    int xset = find(parent, x);

    int yset = find(parent, y);

    parent[xset] = yset;

}

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

Let there be 4 elements 0, 1, 2, 3

Initially, all elements are single element subsets.
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
     2   3   
    /
   1
 /
0

Do Union(2, 3)
         3    
        /
      2
     /
   1
 /
0

Вышеуказанные операции могут быть оптимизированы до O (Log n) в худшем случае. Идея состоит в том, чтобы всегда прикреплять дерево меньшей глубины под корнем более глубокого дерева. Эта техника называется объединением по рангу . Термин ранг предпочтительнее, чем высота, потому что если используется метод сжатия пути (мы обсудили его ниже), то ранг не всегда равен высоте. Кроме того, размер (вместо высоты) деревьев также может быть использован в качестве ранга . Использование размера в качестве ранга также дает сложность времени наихудшего случая как O (Logn) (см. Это для доказательства)

Let us see the above example with union by rank
Initially, all elements are single element subsets.
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
   1    3
 /  \
0    2

Do Union(2, 3)
    1    
 /  |  \
0   2   3

Вторая оптимизация для наивного метода — Сжатие Пути . Идея состоит в том, чтобы сгладить дерево при вызове find () . Когда find () вызывается для элемента x, возвращается корень дерева. Операция find () перемещается вверх от x, чтобы найти root. Идея сжатия пути состоит в том, чтобы сделать найденный корень родительским для x, чтобы нам не приходилось снова проходить все промежуточные узлы. Если x является корнем поддерева, то путь (к корню) из всех узлов в x также сжимается.

     
Let the subset {0, 1, .. 9} be represented as below and find() is called
for element 3.
              9
         /    |    \  
        4     5      6
     /     \        /  \
    0        3     7    8
            /  \
           1    2  

When find() is called for 3, we traverse up and find 9 as representative
of this subset. With path compression, we also make 3 as the child of 9 so 
that when find() is called next time for 1, 2 or 3, the path to root is reduced.

               9
         /    /  \    \
        4    5    6     3 
     /           /  \   /  \
    0           7    8  1   2           

Эти две техники дополняют друг друга. Временная сложность каждой операции становится даже меньше, чем O (Logn). Фактически амортизированная временная сложность фактически становится небольшой постоянной.

Далее следует реализация на основе объединения по рангу и сжатию путей для нахождения цикла в графе.

C ++

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

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

struct Edge

{

    int src, dest;

};

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

struct Graph

{

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

    int V, E;

  

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

    struct Edge* edge;

};

  

struct subset

{

    int parent;

    int rank;

};

  
// Создаем граф с 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(struct subset subsets[], int i)

{

    // найти root и сделать root родителем i (сжатие пути)

    if (subsets[i].parent != i)

        subsets[i].parent = find(subsets, subsets[i].parent);

  

    return subsets[i].parent;

}

  
// Функция, которая объединяет два набора x и y
// (использует объединение по рангу)

void Union(struct subset subsets[], int x, int y)

{

    int xroot = find(subsets, x);

    int yroot = find(subsets, y);

  

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

    // (Объединение по рангу)

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

        subsets[yroot].parent = xroot;

  

    // Если ранги одинаковы, сделать из них корень и увеличить

    // его ранг на единицу

    else

    {

        subsets[yroot].parent = xroot;

        subsets[xroot].rank++;

    }

}

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

int isCycle( struct Graph* graph )

{

    int V = graph->V;

    int E = graph->E;

  

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

    struct subset *subsets =

        (struct subset*) malloc( V * sizeof(struct subset) );

  

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

    {

        subsets[v].parent = v;

        subsets[v].rank = 0;

    }

  

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

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

    // цикл в графе.

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

    {

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

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

  

        if (x == y)

            return 1;

  

        Union(subsets, 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;

}

Джава

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

class Graph

{

int V, E;

Edge[] edge;

  

Graph(int nV, int nE)

{

    V = nV;

    E = nE;

    edge = new Edge[E];

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

    {

        edge[i] = new Edge();

    }

}

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

class Edge

{

    int src, dest;

}

  
// класс для представления подмножества

class subset

{

    int parent;

    int rank;

}

  
// Полезная функция для поиска
// набор элемента i (использует
// метод сжатия пути)

int find(subset [] subsets , int i)

{

if (subsets[i].parent != i)

    subsets[i].parent = find(subsets, 

                             subsets[i].parent);

    return subsets[i].parent;

}

  
// Функция, которая объединяет
// из двух наборов x и y
// (использует объединение по рангу)

void Union(subset [] subsets, 

           int x , int y )

{

    int xroot = find(subsets, x);

        int yroot = find(subsets, y);

  

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[yroot].rank < subsets[xroot].rank)

        subsets[yroot].parent = xroot;

    else

    {

        subsets[xroot].parent = yroot;

        subsets[yroot].rank++;

    }

}

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

int isCycle(Graph graph)

{

    int V = graph.V;

    int E = graph.E;

  

    subset [] subsets = new subset[V];

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

    {

  

        subsets[v] = new subset();

        subsets[v].parent = v;

        subsets[v].rank = 0;

    }

  

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

    {

        int x = find(subsets, graph.edge[e].src);

        int y = find(subsets, graph.edge[e].dest);

        if(x == y)

            return 1;

        Union(subsets, 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");

}
}

  
// Этот код добавлен
// Ашвани Хемани

python3

# Объединение по рангу и сжатию пути на основе
# программа для обнаружения цикла на графике

from collections import defaultdict

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

class Graph:

      

    def __init__(self, num_of_v):

        self.num_of_v = num_of_v

        self.edges = defaultdict(list)

          

    # график представлен в виде

    # массив ребер

    def add_edge(self, u, v):

        self.edges[u].append(v)

  

  

class Subset:

    def __init__(self, parent, rank):

        self.parent = parent

        self.rank = rank

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

def find(subsets, node):

    if subsets[node].parent != node:

        subsets[node].parent = find(subsets, subsets[node].parent)

    return subsets[node].parent

  
# Функция, которая объединяет два набора
# из вас и v (использует объединение по рангу)

def union(subsets, u, v):

      

    # Присоединить дерево меньшего ранга под корнем

    Количество деревьев высокого ранга (Union by Rank)

    if subsets[u].rank > subsets[v].rank:

        subsets[v].parent = u

    elif subsets[v].rank > subsets[u].rank:

        subsets[u].parent = v

          

    # Если ранги одинаковы, то сделать один как

    # корень и увеличить его ранг на единицу

    else:

        subsets[v].parent = u

        subsets[u].rank += 1

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

def isCycle(graph):

      

    # Распределить память для создания наборов

    subsets = []

  

    for u in range(graph.num_of_v):

        subsets.append(Subset(u, 0))

  

    # Перебирать все ребра графа,

    # найти наборы обеих вершин каждого

    # край, если наборы одинаковы, то есть

    # - цикл в графе.

    for u in graph.edges:

        u_rep = find(subsets, u)

  

        for v in graph.edges[u]:

            v_rep = find(subsets, v)

  

            if u_rep == v_rep:

                return True

            else:

                union(subsets, u_rep, v_rep)

  
Код водителя

g = Graph(3)

  
# добавить ребро 0-1

g.add_edge(0, 1)

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

g.add_edge(1, 2)

  
# добавить ребро 0-2

g.add_edge(0, 2)

  

if isCycle(g):

    print('Graph contains cycle')

else:

    print('Graph does not contain cycle')

  
# Этот код предоставлен
# Сампат Кумар Сурин

C #

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

using System; 

  

class Graph 

public int V, E; 

public Edge[] edge; 

  

public Graph(int nV, int nE) 

    V = nV; 

    E = nE; 

    edge = new Edge[E]; 

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

    

        edge[i] = new Edge(); 

    

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

public class Edge 

    public int src, dest; 

  
// класс для представления подмножества

class subset 

    public int parent; 

    public int rank; 

  
// Полезная функция для поиска
// набор элемента i (использует
// метод сжатия пути)

int find(subset []subsets , int i) 

if (subsets[i].parent != i) 

    subsets[i].parent = find(subsets, 

                             subsets[i].parent); 

    return subsets[i].parent; 

  
// Функция, которая объединяет
// из двух наборов x и y
// (использует объединение по рангу)

void Union(subset [] subsets, 

           int x , int y ) 

    int xroot = find(subsets, x); 

        int yroot = find(subsets, y); 

  

    if (subsets[xroot].rank < subsets[yroot].rank) 

        subsets[xroot].parent = yroot; 

    else if (subsets[yroot].rank < subsets[xroot].rank) 

        subsets[yroot].parent = xroot; 

    else

    

        subsets[xroot].parent = yroot; 

        subsets[yroot].rank++; 

    

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

int isCycle(Graph graph) 

    int V = graph.V; 

    int E = graph.E; 

  

    subset [] subsets = new subset[V]; 

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

    

        subsets[v] = new subset(); 

        subsets[v].parent = v; 

        subsets[v].rank = 0; 

    

  

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

    

        int x = find(subsets, graph.edge[e].src); 

        int y = find(subsets, graph.edge[e].dest); 

        if(x == y) 

            return 1; 

        Union(subsets, x, y); 

    

return 0; 

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

static public 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) 

    Console.WriteLine("Graph contains cycle"); 

else

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


  
// Этот код добавлен
// Арнаб Кунду


Выход:

Graph contains cycle

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

Ссылки:
http://en.wikipedia.org/wiki/Disjoint-set_data_structure
IITD Видео Лекция

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

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

Союз-Найти Алгоритм | Набор 2 (объединение по рангу и сжатию пути)

0.00 (0%) 0 votes