递归查找图矩阵DFS中的所有路径DFS

Question

我试图使用递归方法实现基于深度优先搜索的两个函数。我最终试图将运行时与warshall的算法（我已经工作）进行比较。当我打印我的矩阵时，它会被一对关闭的路径关闭。

递归是什么可能会把我扔掉，这是我的弱点。由于顶部if语句if(iIndex1 == iIndex2) return TRUE;，当我尝试查找是否存在来自（A，A），（B，B），（C，C）等的路径时，即使没有路径，我也将始终获得1从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 
     } 
    } 
} 

它应该是

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 

我得到什么

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

您的问题可能在这里：

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

通过在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; 
    } 
} 

也就是说，“如果一个路径确实存在，作为回报我们发现它如果没有，继续找。”

Answer 2

我的深度优先搜索使用递归，但它输出父阵列，虽然功能应该是的AME。它有一个完美的成绩，所以我知道它的工作原理。希望能帮助到你。

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

算法〜

1. 布尔阵列，参观了萎靡不振的节点
2. 搜索数阵列来衡量访问深度
3. 深度递增，并拿出搜索NUM
4. 拨打0.0上的DFS
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; 
   
   };