Dado un gráfico dirigido, averigüe si un vértice j es accesible desde otro vértice i para todos los pares de vértices (i, j) en el gráfico dado. Aquí alcanzable significa que hay un camino desde el vértice i al j. La array de capacidad de alcance se denomina 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
El gráfico se da en forma de array de adyacencia, digamos ‘gráfico [V] [V]’ donde gráfico [i] [j] es 1 si hay un borde desde el vértice i al vértice j o i es igual a j, de lo contrario, grafique [i][j] es 0. Se puede usar
el algoritmo Floyd Warshall , podemos calcular la array de distancia dist[V][V] usando Floyd Warshall , si dist[i][j] es infinito, entonces j no es accesible desde I. De lo contrario, j es alcanzable y el valor de dist[i][j] será menor que V.
En lugar de usar Floyd Warshall directamente, podemos optimizarlo en términos de espacio y tiempo para este problema en particular. Las siguientes son las optimizaciones:
- En lugar de una array resultante entera ( dist[V][V] en floyd warshall ), podemos crear una array booleana de capacidad de alcance alcance[V][V] (ahorramos espacio). El valor alcance[i][j] será 1 si j es accesible desde i, de lo contrario 0.
- En lugar de usar operaciones aritméticas, podemos usar operaciones lógicas. Para operaciones aritméticas se usa ‘+’, lógico y ‘&&’, y para min, lógico o ‘||’ se usa (Ahorramos tiempo por un factor constante. Sin embargo, la complejidad del tiempo es la misma)
A continuación se muestra la implementación del enfoque anterior:
C++
// Program for transitive closure
// using Floyd Warshall Algorithm
#include<stdio.h>
// Number of vertices in the graph
#define V 4
// A function to print the solution matrix
void printSolution(int reach[][V]);
// Prints transitive closure of graph[][]
// using Floyd Warshall algorithm
void transitiveClosure(int graph[][V])
{
/* reach[][] will be the output matrix
// that will finally have the
shortest distances between
every pair of vertices */
int reach[V][V], i, j, k;
/* Initialize the solution matrix same
as input graph matrix. Or
we can say the initial values of
shortest distances are based
on shortest paths considering
no intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
reach[i][j] = graph[i][j];
/* Add all vertices one by one to the
set of intermediate vertices.
---> Before start of a iteration,
we have reachability values for
all pairs of vertices such that
the reachability values
consider only the vertices in
set {0, 1, 2, .. k-1} as
intermediate vertices.
----> After the end of a iteration,
vertex no. k is added to the
set of intermediate vertices
and the set becomes {0, 1, .. k} */
for (k = 0; k < V; k++)
{
// Pick all vertices as
// source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as
// destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on a path
// from i to j,
// then make sure that the value
// of reach[i][j] is 1
reach[i][j] = reach[i][j] ||
(reach[i][k] && reach[k][j]);
}
}
}
// Print the shortest distance matrix
printSolution(reach);
}
/* A utility function to print solution */
void printSolution(int reach[][V])
{
printf ("Following matrix is transitive");
printf("closure of the given graph\n");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
/* because "i==j means same vertex"
and we can reach same vertex
from same vertex. So, we print 1....
and we have not considered this in
Floyd Warshall Algo. so we need to
make this true by ourself
while printing transitive closure.*/
if(i == j)
printf("1 ");
else
printf ("%d ", reach[i][j]);
}
printf("\n");
}
}
// Driver Code
int main()
{
/* Let us create the following weighted graph
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}
};
// Print the solution
transitiveClosure(graph);
return 0;
}
Java
// Program for transitive closure
// using Floyd Warshall Algorithm
import java.util.*;
import java.lang.*;
import java.io.*;
class GraphClosure
{
final static int V = 4; //Number of vertices in a graph
// Prints transitive closure of graph[][] using Floyd
// Warshall algorithm
void transitiveClosure(int graph[][])
{
/* reach[][] will be the output matrix that will finally
have the shortest distances between every pair of
vertices */
int reach[][] = new int[V][V];
int i, j, k;
/* Initialize the solution matrix same as input graph
matrix. Or we can say the initial values of shortest
distances are based on shortest paths considering
no intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
reach[i][j] = graph[i][j];
/* Add all vertices one by one to the set of intermediate
vertices.
---> Before start of a iteration, we have reachability
values for all pairs of vertices such that the
reachability values consider only the vertices in
set {0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of a iteration, vertex no. k is
added to the set of intermediate vertices and the
set becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on a path from i to j,
// then make sure that the value of reach[i][j] is 1
reach[i][j] = (reach[i][j]!=0) ||
((reach[i][k]!=0) && (reach[k][j]!=0))?1:0;
}
}
}
// Print the shortest distance matrix
printSolution(reach);
}
/* A utility function to print solution */
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++) {
if ( i == j)
System.out.print("1 ");
else
System.out.print(reach[i][j]+" ");
}
System.out.println();
}
}
// Driver Code
public static void main (String[] args)
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
/* Let us create the following weighted graph
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}
};
// Print the solution
GraphClosure g = new GraphClosure();
g.transitiveClosure(graph);
}
}
// This code is contributed by Aakash Hasija
Python3
# Python program for transitive closure using Floyd Warshall Algorithm
#Complexity : O(V^3)
from collections import defaultdict
#Class to represent a graph
class Graph:
def __init__(self, vertices):
self.V = vertices
# A utility function to print the solution
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):
if (i == j):
print ("%7d\t" % (1),end=" ")
else:
print ("%7d\t" %(reach[i][j]),end=" ")
print()
# Prints transitive closure of graph[][] using Floyd Warshall algorithm
def transitiveClosure(self,graph):
'''reach[][] will be the output matrix that will finally
have reachability values.
Initialize the solution matrix same as input graph matrix'''
reach =[i[:] for i in graph]
'''Add all vertices one by one to the set of intermediate
vertices.
---> Before start of a iteration, we have reachability value
for all pairs of vertices such that the reachability values
consider only the vertices in set
{0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of an iteration, vertex no. k is
added to the set of intermediate vertices and the
set becomes {0, 1, 2, .. k}'''
for k in range(self.V):
# Pick all vertices as source one by one
for i in range(self.V):
# Pick all vertices as destination for the
# above picked source
for j in range(self.V):
# If vertex k is on a path from i to j,
# then make sure that the value of reach[i][j] is 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]]
#Print the solution
g.transitiveClosure(graph)
#This code is contributed by Neelam Yadav
C#
// C# Program for transitive closure
// using Floyd Warshall Algorithm
using System;
class GFG
{
static int V = 4; // Number of vertices in a graph
// Prints transitive closure of graph[,]
// using Floyd Warshall algorithm
void transitiveClosure(int [,]graph)
{
/* reach[,] will be the output matrix that
will finally have the shortest distances
between every pair of vertices */
int [,]reach = new int[V, V];
int i, j, k;
/* Initialize the solution matrix same as
input graph matrix. Or we can say the
initial values of shortest distances are
based on shortest paths considering no
intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
reach[i, j] = graph[i, j];
/* Add all vertices one by one to the
set of intermediate vertices.
---> Before start of a iteration, we have
reachability values for all pairs of
vertices such that the reachability
values consider only the vertices in
set {0, 1, 2, .. k-1} as intermediate vertices.
---> After the end of a iteration, vertex no.
k is added to the set of intermediate
vertices and the set becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination
// for the above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on a path from i to j,
// then make sure that the value of
// reach[i,j] is 1
reach[i, j] = (reach[i, j] != 0) ||
((reach[i, k] != 0) &&
(reach[k, j] != 0)) ? 1 : 0;
}
}
}
// Print the shortest distance matrix
printSolution(reach);
}
/* A utility function to print solution */
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++){
if (i == j)
Console.Write("1 ");
else
Console.Write(reach[i, j] + " ");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main (String[] args)
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
/* Let us create the following weighted graph
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}};
// Print the solution
GFG g = new GFG();
g.transitiveClosure(graph);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program for transitive closure
// using Floyd Warshall Algorithm
var V = 4; // Number of vertices in a graph
// Prints transitive closure of graph[,]
// using Floyd Warshall algorithm
function transitiveClosure(graph) {
/* reach[,] will be the output matrix that
will finally have the shortest distances
between every pair of vertices */
var reach = Array.from(Array(V), () => new Array(V));
var i, j, k;
/* Initialize the solution matrix same as
input graph matrix. Or we can say the
initial values of shortest distances are
based on shortest paths considering no
intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++) reach[i][j] = graph[i][j];
/* Add all vertices one by one to the
set of intermediate vertices.
---> Before start of a iteration, we have
reachability values for all pairs of
vertices such that the reachability
values consider only the vertices in
set {0, 1, 2, .. k-1} as intermediate vertices.
---> After the end of a iteration, vertex no.
k is added to the set of intermediate
vertices and the set becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination
// for the above picked source
for (j = 0; j < V; j++) {
// If vertex k is on a path from i to j,
// then make sure that the value of
// reach[i,j] is 1
reach[i][j] =
reach[i][j] != 0 || (reach[i][k] != 0 && reach[k][j] != 0)
? 1
: 0;
}
}
}
// Print the shortest distance matrix
printSolution(reach);
}
/* A utility function to print solution */
function printSolution(reach) {
document.write(
"Following matrix is transitive" + " closure of the given graph <br>"
);
for (var i = 0; i < V; i++) {
for (var j = 0; j < V; j++) {
if (i == j) document.write("1 ");
else document.write(reach[i][j] + " ");
}
document.write("<br>");
}
}
// Driver Code
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
var graph = [
[1, 1, 0, 1],
[0, 1, 1, 0],
[0, 0, 1, 1],
[0, 0, 0, 1],
];
// Print the solution
transitiveClosure(graph);
// This code is contributed by rdtank.
</script>
Producción
Following matrix is transitiveclosure of the given graph 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1
Complejidad de tiempo: O(V 3 ) donde V es el número de vértices en el gráfico dado.
Consulte la publicación a continuación para obtener una solución O (V 2 ).
Cierre transitivo de un gráfico usando DFS
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