递归查找图矩阵 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

我的深度优先搜索使用递归，但它输出一个父数组，尽管功能应该是相同的。它获得了完美的成绩，所以我知道它有效。希望对你有帮助。

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

算法~

布尔数组，访问标记节点
搜索数字数组来衡量访问深度
深度增加并得出搜索数
在 0,0 调用 DFS
对于每个未访问的邻居
DFS深度+1，搜索=深度，访问=真

return父数组，显示搜索模式

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

您的问题可能在这里：

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

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

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

Recursion find all paths in graph matrix DFS

c

recursion

matrix

depth-first-search