Dado un gráfico dirigido, averigüe si un vértice v es accesible desde otro vértice u para todos los pares de vértices (u, v) en el gráfico dado. Aquí alcanzable significa que hay un camino desde el vértice u hasta el v. La array de capacidad de alcance se llama cierre transitivo de un gráfico.
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
Hemos discutido una solución O(V 3 ) para esto aquí . La solución se basó en el Algoritmo de Floyd Warshall . En esta publicación, se discute un algoritmo O(V(V+E)) para el mismo. Entonces, para un gráfico denso, se convertiría en O(V 3 ) y para un gráfico disperso, se convertiría en O(V 2 ).
A continuación se muestran los pasos abstractos del algoritmo.
- Cree una array tc[V][V] que finalmente tenga un cierre transitivo del grafo dado. Inicialice todas las entradas de tc[][] como 0.
- Llame a DFS para cada Node del gráfico para marcar los vértices alcanzables en tc[][]. En las llamadas recursivas a DFS, no llamamos a DFS para un vértice adyacente si ya está marcado como accesible en tc[][].
A continuación se muestra la implementación de la idea anterior. El código usa la representación de lista de adyacencia del gráfico de entrada y crea una array tc[V][V] tal que tc[u][v] sería verdadero si v es accesible desde u.
Implementación:
C++
// C++ program to print transitive closure of a graph
#include <bits/stdc++.h>
using namespace std;
class Graph {
int V; // No. of vertices
bool** tc; // To store transitive closure
list<int>* adj; // array of adjacency lists
void DFSUtil(int u, int v);
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int v, int w) { adj[v].push_back(w); }
// prints transitive closure matrix
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));
}
}
// A recursive DFS traversal function that finds
// all reachable vertices for s.
void Graph::DFSUtil(int s, int v)
{
// Mark reachability from s to t as true.
if (s == v) {
tc[s][v] = true;
}
else
tc[s][v] = true;
// Find all the vertices reachable through v
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i) {
if (tc[s][*i] == false) {
if (*i == s) {
tc[s][*i] = 1;
}
else {
DFSUtil(s, *i);
}
}
}
}
// The function to find transitive closure. It uses
// recursive DFSUtil()
void Graph::transitiveClosure()
{
// Call the recursive helper function to print DFS
// traversal starting from all vertices one by one
for (int i = 0; i < V; i++)
DFSUtil(i,
i); // Every vertex is reachable from self.
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++)
cout << tc[i][j] << " ";
cout << endl;
}
}
// Driver code
int main()
{
// Create a graph given in the above diagram
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
// JAVA program to print transitive
// closure of a graph.
import java.util.ArrayList;
import java.util.Arrays;
// A directed graph using
// adjacency list representation
public class Graph {
// No. of vertices in graph
private int vertices;
// adjacency list
private ArrayList<Integer>[] adjList;
// To store transitive closure
private int[][] tc;
// Constructor
public Graph(int vertices) {
// initialise vertex count
this.vertices = vertices;
this.tc = new int[this.vertices][this.vertices];
// initialise adjacency list
initAdjList();
}
// utility method to initialise adjacency list
@SuppressWarnings("unchecked")
private void initAdjList() {
adjList = new ArrayList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new ArrayList<>();
}
}
// add edge from u to v
public void addEdge(int u, int v) {
// Add v to u's list.
adjList[u].add(v);
}
// The function to find transitive
// closure. It uses
// recursive DFSUtil()
public void transitiveClosure() {
// Call the recursive helper
// function to print DFS
// traversal starting from all
// vertices one by one
for (int i = 0; i < vertices; i++) {
dfsUtil(i, i);
}
for (int i = 0; i < vertices; i++) {
System.out.println(Arrays.toString(tc[i]));
}
}
// A recursive DFS traversal
// function that finds
// all reachable vertices for s
private void dfsUtil(int s, int v) {
// Mark reachability from
// s to v as true.
if(s==v){
tc[s][v] = 1;
}
else
tc[s][v] = 1;
// Find all the vertices reachable
// through v
for (int adj : adjList[v]) {
if (tc[s][adj]==0) {
dfsUtil(s, adj);
}
}
}
// Driver Code
public static void main(String[] args) {
// Create a graph given
// in the above diagram
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();
}
}
// This code is contributed
// by Himanshu Shekhar
Python3
# Python program to print transitive # closure of a graph. from collections import defaultdict class Graph: def __init__(self,vertices): # No. of vertices self.V = vertices # default dictionary to store graph self.graph = defaultdict(list) # To store transitive closure self.tc = [[0 for j in range(self.V)] for i in range(self.V)] # function to add an edge to graph def addEdge(self, u, v): self.graph[u].append(v) # A recursive DFS traversal function that finds # all reachable vertices for s def DFSUtil(self, s, v): # Mark reachability from s to v as true. if(s == v): if( v in self.graph[s]): self.tc[s][v] = 1 else: self.tc[s][v] = 1 # Find all the vertices reachable through v for i in self.graph[v]: if self.tc[s][i] == 0: if s==i: self.tc[s][i]=1 else: self.DFSUtil(s, i) # The function to find transitive closure. It uses # recursive DFSUtil() def transitiveClosure(self): # Call the recursive helper function to print DFS # traversal starting from all vertices one by one for i in range(self.V): self.DFSUtil(i, i) print(self.tc) # Create a graph given in the above diagram 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) g.transitiveClosure()
C#
// C# program to print transitive
// closure of a graph.
using System;
using System.Collections.Generic;
// A directed graph using
// adjacency list representation
public class Graph {
// No. of vertices in graph
private int vertices;
// adjacency list
private List<int>[] adjList;
// To store transitive closure
private int[, ] tc;
// Constructor
public Graph(int vertices)
{
// initialise vertex count
this.vertices = vertices;
this.tc = new int[this.vertices, this.vertices];
// initialise adjacency list
initAdjList();
}
// utility method to initialise adjacency list
private void initAdjList()
{
adjList = new List<int>[ vertices ];
for (int i = 0; i < vertices; i++) {
adjList[i] = new List<int>();
}
}
// add edge from u to v
public void addEdge(int u, int v)
{
// Add v to u's list.
adjList[u].Add(v);
}
// The function to find transitive
// closure. It uses
// recursive DFSUtil()
public void transitiveClosure()
{
// Call the recursive helper
// function to print DFS
// traversal starting from all
// vertices one by one
for (int i = 0; i < vertices; i++) {
dfsUtil(i, i);
}
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++)
Console.Write(tc[i, j] + " ");
Console.WriteLine();
}
}
// A recursive DFS traversal
// function that finds
// all reachable vertices for s
private void dfsUtil(int s, int v)
{
// Mark reachability from
// s to v as true.
tc[s, v] = 1;
// Find all the vertices reachable
// through v
foreach(int adj in adjList[v])
{
if (tc[s, adj] == 0) {
dfsUtil(s, adj);
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Create a graph given
// in the above diagram
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);
Console.WriteLine("Transitive closure "
+ "matrix is");
g.transitiveClosure();
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
/* Javascript program to print transitive
closure of a graph*/
class Graph
{
// Constructor
constructor(v)
{
this.V = v;
this.adj = new Array(v);
this.tc = Array.from(Array(v), () => new Array(v).fill(0));
for(let i = 0; i < v; i++)
this.adj[i] = [];
}
// function to add an edge to graph
addEdge(v, w)
{
this.adj[v].push(w);
}
// A recursive DFS traversal function that finds
// all reachable vertices for s.
DFSUtil(s, v)
{
// Mark reachability from s to v as true.
this.tc[s][v] = 1;
// Find all the vertices reachable through v
for(let i of this.adj[v].values())
{
if(this.tc[s][i] == 0)
this.DFSUtil(s, i);
}
}
// The function to find transitive closure. It uses
// recursive DFSUtil()
transitiveClosure()
{
// Call the recursive helper function to print DFS
// traversal starting from all vertices one by one
for(let i = 0; i < this.V; i++)
this.DFSUtil(i, i); // Every vertex is reachable from self
document.write("Transitive closure matrix is<br />")
for(let i=0; i < this.V; i++)
{
for(let j=0; j < this.V; j++)
document.write(this.tc[i][j] + " ");
document.write("<br />")
}
}
};
// driver code
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);
g.transitiveClosure();
// This code is contributed by cavi4762.
</script>
Producción
Transitive closure matrix is 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA