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