Cuente todos los caminos hamiltonianos en un gráfico dirigido dado

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 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].
  • 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *