Dado un gráfico dirigido de N vértices valorados de 0 a N – 1 y el gráfico de array [] de tamaño K representa la lista de adyacencia del gráfico dado , la tarea es contar todos los caminos hamiltonianos que comienzan en el vértice 0 y finalizan en el (N – 1) vértice .
Nota: El camino hamiltoniano se define como el camino que visita cada vértice del gráfico exactamente una vez.
Ejemplos:
Entrada: N = 4, K = 6, gráfico[][] = {{1, 2}, {1, 3}, {2, 3}, {3, 2}, {2, 4}, {3, 4}}
Salida: 2
Explicación:
Las rutas que se muestran a continuación son 1 -> 3 -> 2 -> 4 y 1 -> 2 -> 3 -> 4 comienzan en 1 y terminan en 4 y se denominan rutas hamiltonianas.
Entrada: N = 2, K = 1, gráfico[][] = {{1, 2}}
Salida: 1
Enfoque: el problema dado se puede resolver usando máscara de bits con programación dinámica , e iterar sobre todos los subconjuntos de los vértices dados representados por una máscara de tamaño N y verificar si existe una ruta hamiltoniana que comienza en el vértice 0 y termina en (N – 1) el vértice y contar todos esos caminos. Digamos que para un gráfico que tiene N vértices , S representa una máscara de bits donde S = 0 a S = (1 << N) -1 y dp[i][S] representa el número de caminos que visita cada vértice en la máscara Sy termina en i , entonces la recurrencia válida se dará como dp[i][S] = ∑ dp[j][S XOR 2 i ] donde j ∈ S y hay una arista de j a i donde S XOR 2 i representa el subconjunto que no tiene el i-ésimo vértice y debe haber una arista de j a i . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array 2-D dp[N][2 N ] con 0 y establezca dp[0][1] como 1 .
- Itere sobre el rango de [2, 2 N – 1] usando la variable i y verifique que la máscara tenga todos los bits configurados.
- Iterar sobre el rango de [0, N) usando el extremo variable y atravesar todos los bits de la máscara actual y asumir cada bit como el bit final.
- Inicialice la variable anterior como i – (1 << fin).
- Itere sobre el rango [0, tamaño) donde el tamaño es el tamaño del gráfico de array [fin] usando la variable it y recorra los vértices adyacentes del bit final actual y actualice la array dp [] [] como esta dp [fin ][i] += dp[it][anterior].
- Iterar sobre el rango de [0, N) usando el extremo variable y atravesar todos los bits de la máscara actual y asumir cada bit como el bit final.
- Después de realizar los pasos anteriores, imprima el valor de dp[N-1][2 N – 1] como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all possible paths
void findAllPaths(
int N, vector<vector<int> >& graph)
{
// Initialize a dp array
int dp[N][(1 << N)];
// Initialize it with 0
memset(dp, 0, sizeof dp);
// Initialize for the first vertex
dp[0][1] = 1;
// Iterate over all the masks
for (int i = 2; i < (1 << N); i++) {
// If the first vertex is absent
if ((i & (1 << 0)) == 0)
continue;
// Only consider the full subsets
if ((i & (1 << (N - 1)))
&& i != ((1 << N) - 1))
continue;
// Choose the end city
for (int end = 0; end < N; end++) {
// If this city is not in the subset
if (i & (1 << end) == 0)
continue;
// Set without the end city
int prev = i - (1 << end);
// Check for the adjacent cities
for (int it : graph[end]) {
if ((i & (1 << it))) {
dp[end][i] += dp[it][prev];
}
}
}
}
// Print the answer
cout << dp[N - 1][(1 << N) - 1];
}
// Driver Code
int main()
{
int N = 4;
vector<vector<int> > graph(N);
graph[1].push_back(0);
graph[2].push_back(0);
graph[2].push_back(1);
graph[1].push_back(2);
graph[3].push_back(1);
graph[3].push_back(2);
findAllPaths(N, graph);
return 0;
}
Java
//Java program to count all Hamiltonian
//paths in a given directed graph
import java.io.*;
import java.util.*;
class GFG {
// Function to find all possible paths
static void findAllPaths(int N, List<List<Integer>> graph){
// Initialize a dp array
int dp[][] = new int[N][(1<<N)];
// Initialize it with 0
for(int i=0;i<N;i++){
for(int j=0;j<(1<<N);j++){
dp[i][j]=0;
}
}
// Initialize for the first vertex
dp[0][1] = 1;
// Iterate over all the masks
for (int i = 2; i < (1 << N); i++) {
// If the first vertex is absent
if ((i & (1 << 0)) == 0){
continue;
}
// Only consider the full subsets
if ((i & (1 << (N - 1)))==1 && (i != ((1 << N) - 1))){
continue;
}
// Choose the end city
for (int end = 0; end < N; end++) {
// If this city is not in the subset
if ((i & (1 << end)) == 0){
continue;
}
// Set without the end city
int prev = i - (1 << end);
// Check for the adjacent cities
for (int it : graph.get(end)) {
if ((i & (1 << it))!=0) {
dp[end][i] += dp[it][prev];
}
}
}
}
System.out.print(dp[N - 1][(1 << N) - 1]);
}
//Driver Code
public static void main (String[] args) {
int N=4;
List<List<Integer>> graph = new ArrayList<>();
for(int i=0;i<N;i++){
graph.add(new ArrayList<Integer>());
}
graph.get(1).add(0);
graph.get(2).add(0);
graph.get(2).add(1);
graph.get(1).add(2);
graph.get(3).add(1);
graph.get(3).add(2);
findAllPaths(N, graph);
}
}
//This code is contributed by shruti456rawal
Python3
# python program for the above approach # Function to find all possible paths def findAllPaths(N, graph): # Initialize a dp array # Initialize it with 0 dp = [[0 for _ in range(1 << N)] for _ in range(N)] # Initialize for the first vertex dp[0][1] = 1 # Iterate over all the masks for i in range(2, (1 << N)): # If the first vertex is absent if ((i & (1 << 0)) == 0): continue # Only consider the full subsets if ((i & (1 << (N - 1)))and i != ((1 << N) - 1)): continue # Choose the end city for end in range(0, N): # If this city is not in the subset if (i & (1 << end) == 0): continue # Set without the end city prev = i - (1 << end) # Check for the adjacent cities for it in graph[end]: if ((i & (1 << it))): dp[end][i] += dp[it][prev] # Print the answer print(dp[N - 1][(1 << N) - 1]) # Driver Code if __name__ == "__main__": N = 4 graph = [[] for _ in range(N)] graph[1].append(0) graph[2].append(0) graph[2].append(1) graph[1].append(2) graph[3].append(1) graph[3].append(2) findAllPaths(N, graph) # This code is contributed by rakeshsahni
Javascript
<script>
// Javascript program for the above approach
// Function to find all possible paths
function findAllPaths(N, graph) {
// Initialize a dp array
let dp = new Array(N).fill(0).map(() => new Array(1 << N).fill(0));
// Initialize for the first vertex
dp[0][1] = 1;
// Iterate over all the masks
for (let i = 2; i < 1 << N; i++) {
// If the first vertex is absent
if ((i & (1 << 0)) == 0) continue;
// Only consider the full subsets
if (i & (1 << (N - 1)) && i != (1 << N) - 1) continue;
// Choose the end city
for (let end = 0; end < N; end++) {
// If this city is not in the subset
if (i & (1 << end == 0)) continue;
// Set without the end city
let prev = i - (1 << end);
// Check for the adjacent cities
for (let it of graph[end]) {
if (i & (1 << it)) {
dp[end][i] += dp[it][prev];
}
}
}
}
// Print the answer
document.write(dp[N - 1][(1 << N) - 1]);
}
// Driver Code
let N = 4;
let graph = new Array(N).fill(0).map(() => []);
graph[1].push(0);
graph[2].push(0);
graph[2].push(1);
graph[1].push(2);
graph[3].push(1);
graph[3].push(2);
findAllPaths(N, graph);
// This code is contributed by gfgking.
</script>
2
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA