Dada una array de adyacencia adj[][] de un grafo no dirigido que consta de N vértices, la tarea es encontrar si el grafo contiene un camino hamiltoniano o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Un camino hamiltoniano se define como el camino en un gráfico dirigido o no dirigido que visita todos y cada uno de los vértices del gráfico exactamente una vez.
Ejemplos:
Entrada: adj[][] = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 1}, {1, 0, 1, 0, 0}}
Salida: Sí
Explicación:
existe una ruta hamiltoniana para el gráfico dado, como se muestra en la imagen a continuación:Entrada: adj[][] = {{0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0}}
Salida : No
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las permutaciones posibles de N vértices. Para cada permutación, verifique si es una ruta hamiltoniana válida verificando si hay un borde entre vértices adyacentes o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Complejidad temporal: O(N * N!)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de programación dinámica y enmascaramiento de bits , que se basa en las siguientes observaciones:
- La idea es tal que para todo subconjunto S de vértices, comprobar si existe un camino hamiltoniano en el subconjunto S que termina en el vértice v donde v € S .
- Si v tiene un vecino u , donde u € S – {v} , por lo tanto, existe un camino hamiltoniano que termina en el vértice u .
- El problema se puede resolver generalizando el subconjunto de vértices y el vértice final del camino hamiltoniano.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array booleana dp[][] en dimensión N*2 N donde dp[j ][i] representa si existe o no un camino en el subconjunto representado por la máscara i que visita todos y cada uno de los vértices en i una vez y termina en el vértice j .
- Para el caso base, actualice dp[i][1 << i] = true , for i in range [0, N – 1]
- Iterar sobre el rango [1, 2 N – 1] usando la variable i y realizar los siguientes pasos:
- Todos los vértices con bits establecidos en la máscara i, se incluyen en el subconjunto.
- Itere sobre el rango [1, N] usando la variable j que representará el vértice final de la ruta hamiltoniana de la máscara de subconjunto actual i y realice los siguientes pasos:
- Si el valor de i y 2 j es verdadero, itere sobre el rango [1, N] usando la variable k y si el valor de dp[k][i^2 j ] es verdadero , entonces marque dp[j][ i] es verdadero y sale del bucle .
- De lo contrario, continúe con la siguiente iteración .
- Itere sobre el rango usando la variable i y si el valor de dp[i][2 N – 1] es verdadero , entonces existe un camino hamiltoniano que termina en el vértice i . Por lo tanto, imprima “Sí” . De lo contrario, escriba “No” .
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; const int N = 5; // Function to check whether there // exists a Hamiltonian Path or not bool Hamiltonian_path( vector<vector<int> >& adj, int N) { int dp[N][(1 << N)]; // Initialize the table memset(dp, 0, sizeof dp); // Set all dp[i][(1 << i)] to // true for (int i = 0; i < N; i++) dp[i][(1 << i)] = true; // Iterate over each subset // of nodes for (int i = 0; i < (1 << N); i++) { for (int j = 0; j < N; j++) { // If the jth nodes is included // in the current subset if (i & (1 << j)) { // Find K, neighbour of j // also present in the // current subset for (int k = 0; k < N; k++) { if (i & (1 << k) && adj[k][j] && j != k && dp[k][i ^ (1 << j)]) { // Update dp[j][i] // to true dp[j][i] = true; break; } } } } } // Traverse the vertices for (int i = 0; i < N; i++) { // Hamiltonian Path exists if (dp[i][(1 << N) - 1]) return true; } // Otherwise, return false return false; } // Driver Code int main() { // Input vector<vector<int> > adj = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 0 } }; int N = adj.size(); // Function Call if (Hamiltonian_path(adj, N)) cout << "YES"; else cout << "NO"; return 0; }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to check whether there // exists a Hamiltonian Path or not static boolean Hamiltonian_path(int adj[][], int N) { boolean dp[][] = new boolean[N][(1 << N)]; // Set all dp[i][(1 << i)] to // true for(int i = 0; i < N; i++) dp[i][(1 << i)] = true; // Iterate over each subset // of nodes for(int i = 0; i < (1 << N); i++) { for(int j = 0; j < N; j++) { // If the jth nodes is included // in the current subset if ((i & (1 << j)) != 0) { // Find K, neighbour of j // also present in the // current subset for(int k = 0; k < N; k++) { if ((i & (1 << k)) != 0 && adj[k][j] == 1 && j != k && dp[k][i ^ (1 << j)]) { // Update dp[j][i] // to true dp[j][i] = true; break; } } } } } // Traverse the vertices for(int i = 0; i < N; i++) { // Hamiltonian Path exists if (dp[i][(1 << N) - 1]) return true; } // Otherwise, return false return false; } // Driver Code public static void main(String[] args) { int adj[][] = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 0 } }; int N = adj.length; // Function Call if (Hamiltonian_path(adj, N)) System.out.println("YES"); else System.out.println("NO"); } } // This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to check whether there # exists a Hamiltonian Path or not def Hamiltonian_path(adj, N): dp = [[False for i in range(1 << N)] for j in range(N)] # Set all dp[i][(1 << i)] to # true for i in range(N): dp[i][1 << i] = True # Iterate over each subset # of nodes for i in range(1 << N): for j in range(N): # If the jth nodes is included # in the current subset if ((i & (1 << j)) != 0): # Find K, neighbour of j # also present in the # current subset for k in range(N): if ((i & (1 << k)) != 0 and adj[k][j] == 1 and j != k and dp[k][i ^ (1 << j)]): # Update dp[j][i] # to true dp[j][i] = True break # Traverse the vertices for i in range(N): # Hamiltonian Path exists if (dp[i][(1 << N) - 1]): return True # Otherwise, return false return False # Driver Code adj = [ [ 0, 1, 1, 1, 0 ] , [ 1, 0, 1, 0, 1 ], [ 1, 1, 0, 1, 1 ], [ 1, 0, 1, 0, 0 ] ] N = len(adj) if (Hamiltonian_path(adj, N)): print("YES") else: print("NO") # This code is contributed by maheshwaripiyush9
C#
// C# program for the above approach using System; class GFG{ // Function to check whether there // exists a Hamiltonian Path or not static bool Hamiltonian_path(int[,] adj, int N) { bool[,] dp = new bool[N, (1 << N)]; // Set all dp[i][(1 << i)] to // true for(int i = 0; i < N; i++) dp[i, (1 << i)] = true; // Iterate over each subset // of nodes for(int i = 0; i < (1 << N); i++) { for(int j = 0; j < N; j++) { // If the jth nodes is included // in the current subset if ((i & (1 << j)) != 0) { // Find K, neighbour of j // also present in the // current subset for(int k = 0; k < N; k++) { if ((i & (1 << k)) != 0 && adj[k, j] == 1 && j != k && dp[k, i ^ (1 << j)]) { // Update dp[j][i] // to true dp[j, i] = true; break; } } } } } // Traverse the vertices for(int i = 0; i < N; i++) { // Hamiltonian Path exists if (dp[i, (1 << N) - 1]) return true; } // Otherwise, return false return false; } // Driver Code public static void Main(String[] args) { int[,] adj = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 0 } }; int N = adj.GetLength(0); // Function Call if (Hamiltonian_path(adj, N)) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } // This code is contributed by ukasp
Javascript
<script> // Javascript program for the above approach var N = 5; // Function to check whether there // exists a Hamiltonian Path or not function Hamiltonian_path( adj, N) { var dp = Array.from(Array(N), ()=> Array(1 << N).fill(0)); // Set all dp[i][(1 << i)] to // true for (var i = 0; i < N; i++) dp[i][(1 << i)] = true; // Iterate over each subset // of nodes for (var i = 0; i < (1 << N); i++) { for (var j = 0; j < N; j++) { // If the jth nodes is included // in the current subset if (i & (1 << j)) { // Find K, neighbour of j // also present in the // current subset for (var k = 0; k < N; k++) { if (i & (1 << k) && adj[k][j] && j != k && dp[k][i ^ (1 << j)]) { // Update dp[j][i] // to true dp[j][i] = true; break; } } } } } // Traverse the vertices for (var i = 0; i < N; i++) { // Hamiltonian Path exists if (dp[i][(1 << N) - 1]) return true; } // Otherwise, return false return false; } // Driver Code // Input var adj = [ [ 0, 1, 1, 1, 0 ], [ 1, 0, 1, 0, 1 ], [ 1, 1, 0, 1, 1 ], [ 1, 0, 1, 0, 0 ] ]; var N = adj.length; // Function Call if (Hamiltonian_path(adj, N)) document.write( "YES"); else document.write( "NO"); </script>
YES
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(N * 2 N )
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA