Рубрики

Транзитивное замыкание графа

По заданному ориентированному графу выяснить, достижима ли вершина j из другой вершины i для всех пар вершин (i, j) в данном графе. Здесь достижимо означает, что существует путь от вершины i до j. Матрица достижимости называется транзитивным замыканием графа.

For example, consider below graph

Transitive closure of above graphs is 
     1 1 1 1 
     1 1 1 1 
     1 1 1 1 
     0 0 0 1 

Граф представлен в виде матрицы смежности, скажем, «graph [V] [V]», где graph [i] [j] равен 1, если есть ребро от вершины i до вершины j или i равно j, иначе граф [i] [j] равно 0.

Можно использовать алгоритм Флойда Варшалла , мы можем вычислить матрицу расстояний dist [V] [V], используя Флойд Варшалл , если dist [i] [j] бесконечно, то j не достижимо от i, иначе j достижимо и значение j dist [i] [j] будет меньше, чем V.
Вместо непосредственного использования Floyd Warshall, мы можем оптимизировать его с точки зрения пространства и времени, для этой конкретной проблемы. Ниже приведены оптимизации:

1) Вместо целочисленной результирующей матрицы ( dist [V] [V] в Floyd Warshall ), мы можем создать булеву матрицу достижимых возможностей достижения [V] [V] (мы экономим пространство). Значение достигаемости [i] [j] будет равно 1, если j достижимо от i, иначе 0.

2) Вместо использования арифметических операций мы можем использовать логические операции. Для арифметической операции «+» используется логическое и «&&», а для минимального — логическое или «||» используется. (Мы экономим время постоянным фактором. Хотя сложность времени та же)

C ++

// Программа для транзитивного замыкания с использованием алгоритма Флойда Варшалла
#include<stdio.h>

  
// Количество вершин в графе
#define V 4

  
// Функция для печати матрицы решения

void printSolution(int reach[][V]);

  
// Печатает транзитивное замыкание графа [] [] с использованием алгоритма Флойда Варшалла

void transitiveClosure(int graph[][V])

{

    / * reach [] [] будет выходной матрицей, которая, наконец, будет иметь

       кратчайшие расстояния между каждой парой вершин * /

    int reach[V][V], i, j, k;

  

    / * Инициализировать матрицу решения так же, как матрицу входного графа. Или

       мы можем сказать, что начальные значения кратчайших расстояний основаны

       на кратчайших путях без учета промежуточной вершины. * /

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

        for (j = 0; j < V; j++)

            reach[i][j] = graph[i][j];

  

    / * Добавить все вершины одну за другой в набор промежуточных вершин.

      ---> Перед началом итерации у нас есть значения достижимости для

           все пары вершин, так что значения достижимости

           рассмотрим только вершины из множества {0, 1, 2, .. k-1} как

           промежуточные вершины.

      ----> После окончания итерации вершины нет. к добавляется к

            множество промежуточных вершин и множество становится {0, 1, .. k} * /

    for (k = 0; k < V; k++)

    {

        // Выбрать все вершины как источник по очереди

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

        {

            // Выбрать все вершины в качестве места назначения для

            // выше выбранного источника

            for (j = 0; j < V; j++)

            {

                // Если вершина k находится на пути от i до j,

                // затем убедитесь, что значение reach [i] [j] равно 1

                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

            }

        }

    }

  

    // Распечатать матрицу кратчайшего расстояния

    printSolution(reach);

}

  
/ * Утилита для печати решения * /

void printSolution(int reach[][V])

{

    printf ("Following matrix is transitive closure of the given graph\n");

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

    {

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

            printf ("%d ", reach[i][j]);

        printf("\n");

    }

}

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

int main()

{

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

            10

       (0) -------> (3)

        | / | /

      5 | |

        | | 1

       / | / |

       (1) -------> (2)

            3 * /

    int graph[V][V] = { {1, 1, 0, 1},

                        {0, 1, 1, 0},

                        {0, 0, 1, 1},

                        {0, 0, 0, 1}

                      };

  

    // Распечатать решение

    transitiveClosure(graph);

    return 0;

}

Джава

// Программа для транзитивного замыкания с использованием алгоритма Флойда Варшалла

import java.util.*;

import java.lang.*;

import java.io.*;

  

class GraphClosure

{

    final static int V = 4; // Количество вершин в графе

  

    // Печатает транзитивное замыкание графа [] [] с использованием Floyd

    // алгоритм Варшалла

    void transitiveClosure(int graph[][])

    {

        / * reach [] [] будет выходной матрицей, которая, наконец,

           иметь кратчайшие расстояния между каждой парой

           вершины * /

        int reach[][] = new int[V][V];

        int  i, j, k;

  

        / * Инициализировать матрицу решения так же, как входной граф

           матрица. Или мы можем сказать начальные значения кратчайшего

           расстояния основаны на кратчайших путях с учетом

           промежуточной вершины нет. * /

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

            for (j = 0; j < V; j++)

                reach[i][j] = graph[i][j];

  

        / * Добавить все вершины по одной к набору промежуточных

           Вершины.

          ---> Перед началом итерации мы достижимы

               значения для всех пар вершин, так что

               Значения достижимости учитывают только вершины в

               установите {0, 1, 2, .. k-1} в качестве промежуточных вершин.

          ----> После окончания итерации вершины нет. к есть

                добавляется к набору промежуточных вершин и

                set становится {0, 1, 2, .. k} * /

        for (k = 0; k < V; k++)

        {

            // Выбрать все вершины как источник по очереди

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

            {

                // Выбрать все вершины в качестве места назначения для

                // выше выбранного источника

                for (j = 0; j < V; j++)

                {

                    // Если вершина k находится на пути от i до j,

                    // затем убедитесь, что значение reach [i] [j] равно 1

                    reach[i][j] = (reach[i][j]!=0) ||

                             ((reach[i][k]!=0) && (reach[k][j]!=0))?1:0;

                }

            }

        }

  

        // Распечатать матрицу кратчайшего расстояния

        printSolution(reach);

    }

  

    / * Утилита для печати решения * /

    void printSolution(int reach[][])

    {

        System.out.println("Following matrix is transitive closure"+

                           " of the given graph");

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

        {

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

                System.out.print(reach[i][j]+" ");

            System.out.println();

        }

    }

  

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

    public static void main (String[] args)

    {

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

           10

        (0) -------> (3)

        | / | /

      5 | |

        | | 1

        / | / |

        (1) -------> (2)

           3 * /

  

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

  

              10

         (0) -------> (3)

          | / | /

        5 | |

          | | 1

         / | / |

         (1) -------> (2)

            3 * /

         int graph[][] = new int[][]{ {1, 1, 0, 1},

                                      {0, 1, 1, 0},

                                      {0, 0, 1, 1},

                                      {0, 0, 0, 1}

                                    };

  

         // Распечатать решение

         GraphClosure g = new GraphClosure();

         g.transitiveClosure(graph);

    }

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

питон

# Программа Python для транзитивного замыкания с использованием алгоритма Флойда Варшалла
# Сложность: O (V ^ 3)

  

from collections import defaultdict

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

class Graph:

  

    def __init__(self, vertices):

        self.V = vertices

  

    # Утилита для печати решения

    def printSolution(self, reach):

        print ("Following matrix transitive closure of the given graph ")    

        for i in range(self.V):

            for j in range(self.V):

                print "%7d\t" %(reach[i][j]),

            print ""

      

      

    # Печатает транзитивное замыкание графа [] [] с использованием алгоритма Флойда Варшалла

    def transitiveClosure(self,graph):

        '' 'reach [] [] будет выходной матрицей, которая, наконец,

        имеют значения достижимости.

        Инициализировать матрицу решения так же, как матрицу входного графа '' '

        reach =[i[:] for i in graph]

        '' 'Добавьте все вершины одну за другой к набору промежуточных

        Вершины.

         ---> Перед началом итерации у нас есть значение достижимости

         для всех пар вершин, таких что значения достижимости

          рассмотреть только вершины из множества

        {0, 1, 2, .. k-1} как промежуточные вершины.

          ----> После окончания итерации вершины нет. к есть

         добавляется к набору промежуточных вершин и

        set становится {0, 1, 2, .. k} '' '

        for k in range(self.V):

              

            # Выбрать все вершины как источник один за другим

            for i in range(self.V):

                  

                # Выберите все вершины в качестве пункта назначения для

                # выше выбранного источника

                for j in range(self.V):

                      

                    # Если вершина k находится на пути от i до j,

                       # затем убедитесь, что значение reach [i] [j] равно 1

                    reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

  

        self.printSolution(reach)

          

g= Graph(4)

  

graph = [[1, 1, 0, 1],

         [0, 1, 1, 0],

         [0, 0, 1, 1],

         [0, 0, 0, 1]]

  
# Распечатать решение
g.transitiveClosure(graph)

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

C #

// C # Программа для транзитивного закрытия
// используя алгоритм Флойда Варшалла

using System;

  

class GFG 

    static int V = 4; // Количество вершин в графе

  

    // Печатает транзитивное замыкание графа [,]

    // используя алгоритм Флойда Варшалла

    void transitiveClosure(int [,]graph) 

    

        / * reach [,] будет выходной матрицей, которая

        наконец-то будет иметь самые короткие расстояния

        между каждой парой вершин * /

        int [,]reach = new int[V, V]; 

        int i, j, k; 

  

        / * Инициализировать матрицу решения так же, как

        матрица входного графа. Или мы можем сказать

        начальные значения кратчайших расстояний

        на основе кратчайших путей с учетом нет

        промежуточная вершина. * /

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

            for (j = 0; j < V; j++) 

                reach[i, j] = graph[i, j]; 

  

        / * Добавить все вершины одну за другой в

        множество промежуточных вершин.

        ---> Перед началом итерации имеем

            значения достижимости для всех пар

            вершины такие, что достижимость

            значения учитывают только вершины в

            установите {0, 1, 2, .. k-1} в качестве промежуточных вершин.

        ---> После окончания итерации вершины нет.

             к добавляется набор промежуточных

             вершины и множество становится {0, 1, 2, .. k} * /

        for (k = 0; k < V; k++) 

        

            // Выбрать все вершины как источник по очереди

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

            

                // Выбрать все вершины в качестве пункта назначения

                // для указанного выше источника

                for (j = 0; j < V; j++) 

                

                    // Если вершина k находится на пути от i до j,

                    // затем убедитесь, что значение

                    // достигаем [i, j] 1

                    reach[i, j] = (reach[i, j] != 0) || 

                                 ((reach[i, k] != 0) && 

                                  (reach[k, j] != 0)) ? 1 : 0; 

                

            

        

  

        // Распечатать матрицу кратчайшего расстояния

        printSolution(reach); 

    

  

    / * Утилита для печати решения * /

    void printSolution(int [,]reach) 

    

        Console.WriteLine("Following matrix is transitive"

                          " closure of the given graph"); 

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

        

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

                Console.Write(reach[i, j] + " "); 

            Console.WriteLine(); 

        

    

  

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

    public static void Main (String[] args) 

    

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

        10

        (0) -------> (3)

        | / | /

    5 | |

        | | 1

        / | / |

        (1) -------> (2)

        3 * /

  

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

  

            10

        (0) -------> (3)

        | / | /

        5 | |

        | | 1

        / | / |

        (1) -------> (2)

            3 * /

        int [,]graph = new int[,]{{1, 1, 0, 1}, 

                                  {0, 1, 1, 0}, 

                                  {0, 0, 1, 1}, 

                                  {0, 0, 0, 1}}; 

  

        // Распечатать решение

        GFG g = new GFG(); 

        g.transitiveClosure(graph); 

    

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


Выход:

Following matrix is transitive closure of the given graph
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1

Сложность времени: O (V 3 ) где V — количество вершин в данном графе.

Смотрите ниже пост для решения O (V 2 ).
Транзитивное закрытие графа с использованием DFS

Ссылки:
Введение в алгоритмы от Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л.

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

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

Транзитивное замыкание графа

0.00 (0%) 0 votes