Dado un gráfico dirigido y dos vértices ‘u’ y ‘v’ en él, cuente todos los recorridos posibles desde ‘u’ hasta ‘v’ con exactamente k aristas en el recorrido.
El gráfico recibe una representación de array de adyacencia donde el valor de graph[i][j] como 1 indica que hay un borde desde el vértice i hasta el vértice j y un valor 0 indica que no hay borde desde i hasta j.
Por ejemplo, considere el siguiente gráfico. Deje que la fuente ‘u’ sea el vértice 0, el destino ‘v’ sea 3 y k sea 2. La salida debe ser 2 ya que hay dos recorridos de 0 a 3 con exactamente 2 aristas. Los paseos son {0, 2, 3} y {0, 1, 3}
Enfoque simple : cree una función recursiva que tome el vértice actual, el vértice de destino y el recuento del vértice. Llame a la función recursiva con todos los vértices adyacentes de un vértice actual con el valor de k como k-1. Cuando el valor de k es 0, compruebe si el vértice actual es el destino o no. Si el destino, la respuesta de salida es 1.
La siguiente es la implementación de esta solución simple.
C++
// C++ program to count walks from u to
// v with exactly k edges
#include <iostream>
using namespace std;
// Number of vertices in the graph
#define V 4
// A naive recursive function to count
// walks from u to v with k edges
int countwalks(int graph[][V], int u, int v, int k)
{
// Base cases
if (k == 0 && u == v)
return 1;
if (k == 1 && graph[u][v])
return 1;
if (k <= 0)
return 0;
// Initialize result
int count = 0;
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
if (graph[u][i] == 1) // Check if is adjacent of u
count += countwalks(graph, i, v, k - 1);
return count;
}
// driver program to test above function
int main()
{
/* Let us create the graph shown in above diagram*/
int graph[V][V] = { { 0, 1, 1, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 0 } };
int u = 0, v = 3, k = 2;
cout << countwalks(graph, u, v, k);
return 0;
}
Java
// Java program to count walks from u to v with exactly k edges
import java.util.*;
import java.lang.*;
import java.io.*;
class KPaths {
static final int V = 4; // Number of vertices
// A naive recursive function to count walks from u
// to v with k edges
int countwalks(int graph[][], int u, int v, int k)
{
// Base cases
if (k == 0 && u == v)
return 1;
if (k == 1 && graph[u][v] == 1)
return 1;
if (k <= 0)
return 0;
// Initialize result
int count = 0;
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
if (graph[u][i] == 1) // Check if is adjacent of u
count += countwalks(graph, i, v, k - 1);
return count;
}
// Driver method
public static void main(String[] args) throws java.lang.Exception
{
/* Let us create the graph shown in above diagram*/
int graph[][] = new int[][] { { 0, 1, 1, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 0 } };
int u = 0, v = 3, k = 2;
KPaths p = new KPaths();
System.out.println(p.countwalks(graph, u, v, k));
}
} // Contributed by Aakash Hasija
Python3
# Python3 program to count walks from # u to v with exactly k edges # Number of vertices in the graph V = 4 # A naive recursive function to count # walks from u to v with k edges def countwalks(graph, u, v, k): # Base cases if (k == 0 and u == v): return 1 if (k == 1 and graph[u][v]): return 1 if (k <= 0): return 0 # Initialize result count = 0 # Go to all adjacents of u and recur for i in range(0, V): # Check if is adjacent of u if (graph[u][i] == 1): count += countwalks(graph, i, v, k-1) return count # Driver Code # Let us create the graph shown in above diagram graph = [[0, 1, 1, 1, ], [0, 0, 0, 1, ], [0, 0, 0, 1, ], [0, 0, 0, 0] ] u = 0; v = 3; k = 2 print(countwalks(graph, u, v, k)) # This code is contributed by Smitha Dinesh Semwal.
C#
// C# program to count walks from u to
// v with exactly k edges
using System;
class GFG {
// Number of vertices
static int V = 4;
// A naive recursive function to
// count walks from u to v with
// k edges
static int countwalks(int[, ] graph, int u,
int v, int k)
{
// Base cases
if (k == 0 && u == v)
return 1;
if (k == 1 && graph[u, v] == 1)
return 1;
if (k <= 0)
return 0;
// Initialize result
int count = 0;
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
// Check if is adjacent of u
if (graph[u, i] == 1)
count += countwalks(graph, i, v, k - 1);
return count;
}
// Driver method
public static void Main()
{
/* Let us create the graph shown
in above diagram*/
int[, ] graph = new int[, ] { { 0, 1, 1, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 0 } };
int u = 0, v = 3, k = 2;
Console.Write(
countwalks(graph, u, v, k));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to count walks from u
// to v with exactly k edges
// Number of vertices in the graph
$V = 4;
// A naive recursive function to count
// walks from u to v with k edges
function countwalks( $graph, $u, $v, $k)
{
global $V;
// Base cases
if ($k == 0 and $u == $v)
return 1;
if ($k == 1 and $graph[$u][$v])
return 1;
if ($k <= 0)
return 0;
// Initialize result
$count = 0;
// Go to all adjacents of u and recur
for ( $i = 0; $i < $V; $i++)
// Check if is adjacent of u
if ($graph[$u][$i] == 1)
$count += countwalks($graph, $i,
$v, $k - 1);
return $count;
}
// Driver Code
/* Let us create the graph
shown in above diagram*/
$graph = array(array(0, 1, 1, 1),
array(0, 0, 0, 1),
array(0, 0, 0, 1),
array(0, 0, 0, 0));
$u = 0; $v = 3; $k = 2;
echo countwalks($graph, $u, $v, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to count walks from u to
// v with exactly k edges
// Number of vertices in the graph
var V = 4
// A naive recursive function to count
// walks from u to v with k edges
function countwalks(graph, u, v, k)
{
// Base cases
if (k == 0 && u == v)
return 1;
if (k == 1 && graph[u][v])
return 1;
if (k <= 0)
return 0;
// Initialize result
var count = 0;
// Go to all adjacents of u and recur
for (var i = 0; i < V; i++)
if (graph[u][i] == 1) // Check if is adjacent of u
count += countwalks(graph, i, v, k - 1);
return count;
}
// driver program to test above function
/* Let us create the graph shown in above diagram*/
var graph = [[0, 1, 1, 1, ],
[0, 0, 0, 1, ],
[0, 0, 0, 1, ],
[0, 0, 0, 0] ];
var u = 0, v = 3, k = 2;
document.write(countwalks(graph, u, v, k));
// This code contributed by shubhamsingh10
</script>
Producción
2
Análisis de Complejidad:
- Complejidad temporal: O(V k ).
La complejidad temporal en el peor de los casos de la función anterior es O(V k ) donde V es el número de vértices en el gráfico dado. Simplemente podemos analizar la complejidad del tiempo dibujando un árbol de recursión. Lo peor ocurre para un gráfico completo. En el peor de los casos, cada Node interno del árbol recursivo tendría exactamente n hijos. - Espacio Auxiliar: O(V).
Para almacenar el espacio de pila y la array visitada, se necesita espacio O (V).
Enfoque eficiente: la solución se puede optimizar mediante la programación dinámica . La idea es construir una tabla 3D donde la primera dimensión es el origen, la segunda dimensión es el destino, la tercera dimensión es el número de aristas desde el origen hasta el destino, y el valor es el conteo de caminatas. Como otros problemas de Programación Dinámica , llenan la tabla 3D de forma ascendente.
C++
// C++ program to count walks from
// u to v with exactly k edges
#include <iostream>
using namespace std;
// Number of vertices in the graph
#define V 4
// A Dynamic programming based function to count walks from u
// to v with k edges
int countwalks(int graph[][V], int u, int v, int k)
{
// Table to be filled up using DP.
// The value count[i][j][e] will
// store count of possible walks from
// i to j with exactly k edges
int count[V][V][k + 1];
// Loop for number of edges from 0 to k
for (int e = 0; e <= k; e++) {
for (int i = 0; i < V; i++) // for source
{
for (int j = 0; j < V; j++) // for destination
{
// initialize value
count[i][j][e] = 0;
// from base cases
if (e == 0 && i == j)
count[i][j][e] = 1;
if (e == 1 && graph[i][j])
count[i][j][e] = 1;
// go to adjacent only when the
// number of edges is more than 1
if (e > 1) {
for (int a = 0; a < V; a++) // adjacent of source i
if (graph[i][a])
count[i][j][e] += count[a][j][e - 1];
}
}
}
}
return count[u][v][k];
}
// driver program to test above function
int main()
{
/* Let us create the graph shown in above diagram*/
int graph[V][V] = { { 0, 1, 1, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 0 } };
int u = 0, v = 3, k = 2;
cout << countwalks(graph, u, v, k);
return 0;
}
Java
// Java program to count walks from
// u to v with exactly k edges
import java.util.*;
import java.lang.*;
import java.io.*;
class KPaths {
static final int V = 4; // Number of vertices
// A Dynamic programming based function to count walks from u
// to v with k edges
int countwalks(int graph[][], int u, int v, int k)
{
// Table to be filled up using DP. The value count[i][j][e]
// will/ store count of possible walks from i to j with
// exactly k edges
int count[][][] = new int[V][V][k + 1];
// Loop for number of edges from 0 to k
for (int e = 0; e <= k; e++) {
for (int i = 0; i < V; i++) // for source
{
for (int j = 0; j < V; j++) // for destination
{
// initialize value
count[i][j][e] = 0;
// from base cases
if (e == 0 && i == j)
count[i][j][e] = 1;
if (e == 1 && graph[i][j] != 0)
count[i][j][e] = 1;
// go to adjacent only when number of edges
// is more than 1
if (e > 1) {
for (int a = 0; a < V; a++) // adjacent of i
if (graph[i][a] != 0)
count[i][j][e] += count[a][j][e - 1];
}
}
}
}
return count[u][v][k];
}
// Driver method
public static void main(String[] args) throws java.lang.Exception
{
/* Let us create the graph shown in above diagram*/
int graph[][] = new int[][] { { 0, 1, 1, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 0 } };
int u = 0, v = 3, k = 2;
KPaths p = new KPaths();
System.out.println(p.countwalks(graph, u, v, k));
}
} // Contributed by Aakash Hasija
Python3
# Python3 program to count walks from # u to v with exactly k edges # Number of vertices V = 4 # A Dynamic programming based function # to count walks from u to v with k edges def countwalks(graph, u, v, k): # Table to be filled up using DP. # The value count[i][j][e] will/ # store count of possible walks # from i to j with exactly k edges count = [[[0 for k in range(k + 1)] for i in range(V)] for j in range(V)] # Loop for number of edges from 0 to k for e in range(0, k + 1): # For Source for i in range(V): # For Destination for j in range(V): # Initialize value # count[i][j][e] = 0 # From base cases if (e == 0 and i == j): count[i][j][e] = 1 if (e == 1 and graph[i][j] != 0): count[i][j][e] = 1 # Go to adjacent only when number # of edges is more than 1 if (e > 1): for a in range(V): # Adjacent of i if (graph[i][a] != 0): count[i][j][e] += count[a][j][e - 1] return count[u][v][k] # Driver code if __name__ == '__main__': # Let us create the graph shown # in above diagram graph = [[0, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 0]] u = 0 v = 3 k = 2 print(countwalks(graph, u, v, k)) # This code is contributed by Rajput-Ji
C#
// C# program to count walks from u to v
// with exactly k edges
using System;
class GFG {
static int V = 4; // Number of vertices
// A Dynamic programming based function
// to count walks from u to v with k edges
static int countwalks(int[, ] graph, int u,
int v, int k)
{
// Table to be filled up using DP. The
// value count[i][j][e] will/ store
// count of possible walks from i to
// j with exactly k edges
int[,, ] count = new int[V, V, k + 1];
// Loop for number of edges from 0 to k
for (int e = 0; e <= k; e++) {
// for source
for (int i = 0; i < V; i++) {
// for destination
for (int j = 0; j < V; j++) {
// initialize value
count[i, j, e] = 0;
// from base cases
if (e == 0 && i == j)
count[i, j, e] = 1;
if (e == 1 && graph[i, j] != 0)
count[i, j, e] = 1;
// go to adjacent only when
// number of edges
// is more than 1
if (e > 1) {
// adjacent of i
for (int a = 0; a < V; a++)
if (graph[i, a] != 0)
count[i, j, e] += count[a, j, e - 1];
}
}
}
}
return count[u, v, k];
}
// Driver method
public static void Main()
{
/* Let us create the graph shown in
above diagram*/
int[, ] graph = { { 0, 1, 1, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 1 },
{ 0, 0, 0, 0 } };
int u = 0, v = 3, k = 2;
Console.WriteLine(
countwalks(graph, u, v, k));
}
}
// This is Code Contributed by anuj_67.
Javascript
<script>
// Javascript program to count walks from
// u to v with exactly k edges
// Number of vertices in the graph
var V = 4
// A Dynamic programming based function to count walks from u
// to v with k edges
function countwalks(graph, u, v, k)
{
// Table to be filled up using DP.
// The value count[i][j][e] will
// store count of possible walks from
// i to j with exactly k edges
var count = new Array(V);
for (var i = 0; i <V; i++) {
count[i] = new Array(V);
for (var j = 0; j < V; j++) {
count[i][j] = new Array(V);
for (var e = 0; e <= k; e++) {
count[i][j][e] = 0;
}
}
}
// Loop for number of edges from 0 to k
for (var e = 0; e <= k; e++) {
for (var i = 0; i < V; i++) // for source
{
for (var j = 0; j < V; j++) // for destination
{
// initialize value
count[i][j][e] = 0;
// from base cases
if (e == 0 && i == j)
count[i][j][e] = 1;
if (e == 1 && graph[i][j])
count[i][j][e] = 1;
// go to adjacent only when the
// number of edges is more than 1
if (e > 1) {
for (var a = 0; a < V; a++) // adjacent of source i
if (graph[i][a])
count[i][j][e] += count[a][j][e - 1];
}
}
}
}
return count[u][v][k];
}
// driver program to test above function
/* Let us create the graph shown in above diagram*/
var graph = [ [ 0, 1, 1, 1 ],
[ 0, 0, 0, 1 ],
[ 0, 0, 0, 1 ],
[ 0, 0, 0, 0 ] ];
var u = 0, v = 3, k = 2;
document.write(countwalks(graph, u, v, k));
// This code is contributed by ShubhamSingh10
</script>
Producción
2
Análisis de Complejidad:
- Complejidad Temporal: O(V 3 ).
Se necesitan tres bucles anidados para llenar la tabla DP, por lo que la complejidad del tiempo es O(V 3 ). - Espacio Auxiliar: O(V 3 ).
Para almacenar la tabla DP O(V 3 ) se necesita espacio.
También podemos usar Divide and Conquer para resolver el problema anterior en tiempo O(V 3 Logk). El recuento de caminatas de longitud k de u a v es la [u][v]’ésima entrada en (graph[V][V]) k . Podemos calcular la potencia haciendo la multiplicación O(Logk) usando la técnica de divide y vencerás para calcular la potencia . Una multiplicación entre dos arrays de tamaño V x V toma O(V 3 ) tiempo.
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