Рубрики

Транзитивное закрытие графа с использованием DFS

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

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 

Мы обсудили решение O (V 3 ) для этого здесь . Решение было основано на алгоритме Флойда Варшалла . В этом посте обсуждается алгоритм O (V 2 ) для того же самого.

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

  1. Создайте матрицу tc [V] [V], которая в конечном итоге имела бы транзитивное замыкание данного графа. Инициализируйте все записи tc [] [] как 0.
  2. Вызовите DFS для каждого узла графа, чтобы отметить достижимые вершины в tc [] []. В рекурсивных вызовах DFS мы не вызываем DFS для смежной вершины, если она уже помечена как достижимая в tc [] [].

Ниже приведена реализация вышеуказанной идеи. Код использует представление списка смежности входного графа и строит матрицу tc [V] [V] так, чтобы tc [u] [v] было бы истинным, если v достижим от u.

C / C ++

// C ++ программа для печати транзитивного замыкания графа
#include<bits/stdc++.h>

using namespace std;

  

class Graph

{

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

    bool **tc; // Хранить транзитивное замыкание

    list<int> *adj; // массив списков смежности

    void DFSUtil(int u, int v);

public:

    Graph(int V); // Конструктор

  

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

    void addEdge(int v, int w) { adj[v].push_back(w); }

  

    // печатает матрицу транзитивного замыкания

    void transitiveClosure();

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

  

    tc = new bool* [V];

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

    {

        tc[i] = new bool[V];

        memset(tc[i], false, V*sizeof(bool));

    }

}

  
// Рекурсивная функция обхода DFS, которая находит
// все достижимые вершины для s.

void Graph::DFSUtil(int s, int v)

{

    // Пометить достижимость от s до t как true.

    tc[s][v] = true;

  

    // Найти все вершины, доступные через v

    list<int>::iterator i;

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

        if (tc[s][*i] == false)

            DFSUtil(s, *i);

}

  
// Функция поиска транзитивного замыкания. Оно использует
// рекурсивный DFSUtil ()

void Graph::transitiveClosure()

{

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

    // обход, начиная со всех вершин по одной

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

        DFSUtil(i, i); // Каждая вершина достижима от себя.

  

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

    {

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

            cout << tc[i][j] << " ";

        cout << endl;

    }

}

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

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);

  

    cout << "Transitive closure matrix is \n";

    g.transitiveClosure();

  

    return 0;

}

Джава

// JAVA-программа для печати переходных
// закрытие графа.

  

import java.util.ArrayList;

import java.util.Arrays;

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

public class Graph {

  

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

    private int vertices; 

  

        // список смежности

    private ArrayList<Integer>[] adjList;

  

        // Хранить транзитивное замыкание

    private int[][] tc;

  

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

    public Graph(int vertices) {

  

             // инициализировать количество вершин

             this.vertices = vertices; 

             this.tc = new int[this.vertices][this.vertices];

  

             // инициализировать список смежности

             initAdjList(); 

    }

  

    // служебный метод для инициализации списка смежности

    @SuppressWarnings("unchecked")

    private void initAdjList() {

  

        adjList = new ArrayList[vertices];

        for (int i = 0; i < vertices; i++) {

            adjList[i] = new ArrayList<>();

        }

    }

  

    // добавить ребро от u до v

    public void addEdge(int u, int v) {

                   

      // Добавить v в список u.

        adjList[u].add(v); 

    }

  

    // Функция поиска транзитива

    // закрытие Оно использует

    // рекурсивный DFSUtil ()

    public void transitiveClosure() {

  

        // Вызов рекурсивного помощника

        // функция для печати DFS

        // обход, начиная со всех

        // вершины одна за другой

        for (int i = 0; i < vertices; i++) {

            dfsUtil(i, i);

        }

  

        for (int i = 0; i < vertices; i++) {

          System.out.println(Arrays.toString(tc[i]));

        }

    }

  

    // Рекурсивный обход DFS

    // функция, которая находит

    // все достижимые вершины для s

    private void dfsUtil(int s, int v) {

  

        // Отметить достижимость от

        // с v как истина.

        tc[s][v] = 1;

          

        // Найти все достижимые вершины

        // через v

        for (int adj : adjList[v]) {            

            if (tc[s][adj]==0) {

                dfsUtil(s, adj);

            }

        }

    }

      

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

    public static void main(String[] args) {

  

        // Создать график

        // на схеме выше

        Graph g = new Graph(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);

        System.out.println("Transitive closure " +

                "matrix is");

  

        g.transitiveClosure();

  

    }

}

  

  
// Этот код добавлен
// Химаншу Шехар

питон

# Программа Python для печати транзитивного замыкания графа

from collections import defaultdict

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

class Graph:

  

    def __init__(self,vertices):

        # Количество вершин

        self.V= vertices

  

        # словарь по умолчанию для хранения графика

        self.graph= defaultdict(list)

  

        # Хранить транзитивное замыкание

        self.tc = [[0 for j in range(self.V)] for i in range(self.V)]

  

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

    def addEdge(self,u,v):

        self.graph[u].append(v)

  

    # Рекурсивная функция обхода DFS, которая находит

    # все достижимые вершины для s

    def DFSUtil(self,s,v):

  

        # Отметить достижимость от s до v как true.

        self.tc[s][v] = 1

  

        # Найти все вершины, доступные через v

        for i in self.graph[v]:

            if self.tc[s][i]==0:

                self.DFSUtil(s,i)

  

    # Функция поиска транзитивного замыкания. Оно использует

    # рекурсивный DFSUtil ()

    def transitiveClosure(self):

  

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

        # обход, начиная со всех вершин по одной

        for i in range(self.V):

            self.DFSUtil(i, i)

        print self.tc

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

g = Graph(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)

  

print "Transitive closure matrix is"

g.transitiveClosure();

  
# Этот код предоставлен Neelam Yadav


Выход:

Transitive closure matrix is 
1 1 1 1 
1 1 1 1 
1 1 1 1 
0 0 0 1 

Ссылки:
http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/digraph.4up.pdf

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

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

Транзитивное закрытие графа с использованием DFS

0.00 (0%) 0 votes