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

Question

我正在尝试使用递归方法实现基于深度优先搜索的两个函数。我最终试图将运行时间与 warshall 算法(我已经在工作)进行比较。当我打印矩阵时，它会偏离几个路径。

递归可能会让我失望，这是我的弱点。由于顶部的 if 语句 if(iIndex1 == iIndex2) return TRUE;，当我尝试查找是否存在来自 (A,A)、(B,B)、(C, C) 等。即使没有从 A 到 A 的路径，我也总是会得到 1。

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

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

也就是说，“如果路径确实存在，则返回我们找到的路径。如果不存在，则继续寻找”。