Recursion find all paths in graph matrix DFS

Question

I'm trying to implement a two functions based on Depth First Search using a recursion method. I'm ultimately trying to compare the runtime against warshall's algorithm (which I already have working). When I print my matrix it's off by a couple off paths.

The recursion is what may be throwing me off, it's my weakness. Because of the top if statement if(iIndex1 == iIndex2) return TRUE;, when I try to find if there is a path from (A,A), (B,B), (C,C), etc. I will always get 1 even if there is no path from A to 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
        }
    }
}

what it should be

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 

what I get

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

My depth first search uses recursion but it outputs a parent array, though the functionality should be the same. It got a perfect grade so I know it works. Hope it helps.

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

Algorithm~

1. bool array, visited for flagging nodes
2. search number array to measure the depth of access
3. depth to increment and come up with search num
4. Call DFS on 0,0
5. For each non visited neighbor
6. DFS depth + 1, search = depth, visited = true

7. return parent array, showing the search pattern

   // 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;
   
   };
   

Answer 2

Your issue may be here:

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

By returning the result of recursing on recPathExists, you're not checking the other possible nodes that could be reachable in the loop (in essence, you're returning failure too early, and missing possible paths).

I believe you want just a little 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;
    }
}

That is, "if a path does exist, return as we've found it. If not, keep looking".