La récursion trouve tous les chemins dans la matrice de graphe DFS

Question

J'essaie d'implémenter deux fonctions basées sur Depth First Search en utilisant une méthode de récurrence. J'essaie finalement de comparer l'exécution contre l'algorithme de warshall (que j'ai déjà travaillé). Quand j'imprime ma matrice, elle est coupée par deux chemins.

La récursivité est ce qui peut me jeter, c'est ma faiblesse. En raison de l'instruction top if if(iIndex1 == iIndex2) return TRUE;, quand j'essaie de trouver s'il y a un chemin de (A, A), (B, B), (C, C), etc. Je vais toujours obtenir 1 même s'il n'y a pas de chemin de a à A.

typedef enum { FALSE, TRUE } bool; 

/* Recursive function will determine if there is a path from index 1 to 2 
* Based of DFS 
*/ 
bool recPathExists(Graph G, int iIndex1, int iIndex2) 
{ 
    int j; 
    G.nodeArray[iIndex1].visited = TRUE; 
    if(iIndex1 == iIndex2){ 
      return TRUE; 
    } 
    for(j = 0; j < G.iNumNodes; j++){ 
     if(!G.nodeArray[j].visited && G.adjMatrix[iIndex1][j]==1){ 
      if(recPathExists(G, j, iIndex2)) 
       return TRUE; 
     } 
    } 
    return FALSE; 
} 

/* Write a function to find all pairs of nodes which have paths between them. 
* Store this information in the provided pathMatrix. 
*/ 
void allPathsRecFunc(Graph G , int **pathMatrix) 
{ 
    int i, j; 
    for(i = 0; i < G.iNumNodes; i++){ 
     for(j = 0; j < G.iNumNodes; j++){ 
      if(recPathExists(G, i , j)== TRUE){ 
       pathMatrix[i][j] = 1; 
      } 
      resetVisited(G); //resets all nodes to FALSE 
     } 
    } 
} 

ce qu'elle devrait être

A 0 1 1 1 1 1 1 1 
B 0 1 0 0 1 1 1 1 
C 0 1 0 0 1 1 1 1 
D 0 0 0 0 0 0 0 0 
E 0 0 0 0 0 0 0 0 
F 0 1 0 0 1 1 1 1 
G 0 1 0 0 1 1 1 1 
H 0 1 0 0 1 1 1 1 

ce que je reçois

A 1 1 1 1 1 1 1 1 
B 0 1 0 0 1 1 1 1 
C 0 1 1 0 1 1 1 1 
D 0 0 0 1 0 0 0 0 
E 0 0 0 0 1 0 0 0 
F 0 1 0 0 1 1 1 1 
G 0 1 0 0 1 1 1 1 
H 0 1 0 0 1 1 1 1 

Answer 1

Votre problème peut être ici:

for(j = 0; j < G.iNumNodes; j++) 
{ 
    if(!G.nodeArray[j].visited && G.adjMatrix[iIndex1][j] == 1) 
    { 
     return recPathExists(G, j, iIndex2); 
    } 
} 

Par return le résultat de récursif sur recPathExists, vous ne vérifiez pas les autres nœuds possibles qui pourraient être joignables dans la boucle (en substance, vous êtes retourner l'échec trop tôt, et manquer les chemins possibles).

Je crois que vous voulez juste une petite modification:

for(j = 0; j < G.iNumNodes; j++) 
{ 
    if(!G.nodeArray[j].visited && G.adjMatrix[iIndex1][j] == 1) 
    { 
     if (recPathExists(G, j, iIndex2)) 
      return TRUE; 
    } 
} 

C'est, « si un chemin existe, de retour comme nous l'avons trouvé Dans le cas contraire, continuer à chercher. ».

Answer 2

Ma profondeur première recherche utilise la récursivité, mais il délivre un tableau de parent, bien que la fonctionnalité devrait sois le s ame. Il a obtenu une note parfaite, donc je sais que ça fonctionne. J'espère que cela aide.

https://github.com/grantSwalwell/Data-Structures/blob/master/Depth%20First%20Search.h

algorithme ~

1. tableau de bool, a visité pour les noeuds signalement
2. tableau de numéro de recherche pour mesurer la profondeur de l'accès
3. profondeur pour incrémenter et arriver à la recherche num
4. Appelez DFS sur 0,0
5. Pour chaque voisin non visité
6. DFS profondeur + 1, recherche = profondeur, a visité = true

7. tableau parent de retour, montrant le motif de recherche

   // Depth First Search recursive helper method 
   
   
   void DFS(Graph& G, int v0, Array<bool>* visited, Array<int>* search, int 
   depth) 
   { 
   
       // set visited 
       (*visited)[v0] = true; 
   
       // set search num 
       (*search)[v0] = depth; 
   
       // iterate through neighbors 
       for (int i = 0; i < G.nodes(); i++) 
       { 
        // if i is a neighbor 
        if (G.edge(i, v0)) 
        { 
         // if it has not been visited 
         if (!(*visited)[i]) 
         { 
          // call DFS 
          DFS(G, i, visited, search, depth + 1); 
         } 
        } // end if 
       } // end for 
   } 
   
   // Depth First Search 
   Array<int>* DFS(Graph& G, int v0) 
   { 
   
       // visited array 
       Array<bool>* visited = new Array<bool>(G.nodes()); 
   
       // search number array, order of visitation 
       Array<int>* search = new Array<int>(G.nodes()); 
   
       // initialize both arrays 
       for (int i = 0; i < G.nodes(); i++) 
       { 
        (*visited)[i] = false; 
        (*search)[i] = 1; 
       } 
   
       // create depth field 
       int depth = 1; 
   
       // call DFS 
       DFS(G, v0, visited, search, depth); 
   
       return search; 
   
   };