Рекурсия находит все пути в матрице графа DFS

Ваша проблема может быть здесь:

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

Выполняя returnобработку результата рекурсии на recPathExists, вы не проверяете другие возможные узлы, которые могут быть доступны в цикле (по сути, вы слишком рано возвращаете ошибку и пропускаете возможные пути).

Я считаю, что вам нужна небольшая модификация:

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

То есть «если путь существует, вернитесь в том виде, в котором мы его нашли. Если нет, продолжайте искать».

Мой поиск в глубину использует рекурсию, но выводит родительский массив, хотя функциональность должна быть такой же. Он получил отличную оценку, поэтому я знаю, что это работает. Надеюсь, поможет.

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

Алгоритм~

1. логический массив, посещаемый для пометки узлов
2. массив поисковых номеров для измерения глубины доступа
3. глубину для увеличения и придумать номер поиска
4. Вызов DFS на 0,0
5. За каждого не посещенного соседа
6. Глубина DFS + 1, поиск = глубина, посещено = истина

7. вернуть родительский массив, показывающий шаблон поиска

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