遞歸查找圖矩陣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; 
   
   };