Trouver tous les chemins entre deux nœuds dans un graphique

Question

Voici comment mon graphique est défini.

std::map< std::string, std::set<std::string> > g_db;

et après comment je l'ai fonction écrite pour calculer tous les chemins entre deux nœuds, basé sur une partie de la question précédente sur ce site.

void compute_all_paths(std::vector<std::string>& visited, std::string& dest) { 
    std::string back   = visited.back();  
    std::set<std::string> adj_stations = g_db.find(back)->second; 

    for (std::set<std::string>::iterator itr = adj_stations.begin(); itr != adj_stations.end(); ++itr) { 
     if (std::find(visited.begin(), visited.end(), *itr) != visited.end()) 
      continue; 
     if (*itr == dest) { 
      visited.push_back(*itr);  
      for (std::vector<std::string>::size_type idx = 0; idx < visited.size(); idx++){ 
       std::cout << visited[idx] << " "; 
      } 
      std::cout << std::endl; 
      visited.erase(visited.begin() + (visited.size() - 1));  
      break; 
     } 
    } 
    for (std::set<std::string>::iterator itr = adj_stations.begin(); itr != adj_stations.end(); itr++) { 
     if (std::find(visited.begin(), visited.end(), *itr) != visited.end() || *itr == dest) 
      continue; 
     visited.push_back(*itr);  
     compute_all_paths(visited, dest);    
     visited.erase(visited.begin() + (visited.size() - 1)); 
    } 
} 

Mon graphique est très grande, cette fonction se bloque avec une énorme liste des appels à recursive fonction avec le message suivant:

exception non gérée à 0x7c812afb dans Railways.exe: Microsoft C++ exception: std :: bad_alloc à l'emplacement de mémoire 0x00033748

pour petit graphique cela fonctionne très bien, mais pas pour le graphique énorme.

Quelqu'un peut-il m'aider à trouver le problème?

Answer 1

Un trop grand nombre de niveaux de récursivité peut provoquer un blocage de débordement de pile. C'est pourquoi la récursivité n'est pas bien adaptée aux grands ensembles de données.

Mais tous les appels récursifs peuvent être réduits en boucles. Vous devriez essayer d'enlever les appels récursifs et les remplacer par des boucles.