如何使 DFS 算法继续在图上工作

Question

我正在尝试在 40 x 20 图表上搜索路径（不必是最短路径）。起点和终点是随机选择的。 DFS 工作正常，直到它命中并边缘化。然后，它不会返回并尝试在不同的方向上搜索，它只是循环自己。这是我的代码（一小部分，但不再需要理解它，完整代码在这里：

struct Wierzcholek {
    Wierzcholek* next;
    int numerwierzcholka;
};
bool DFS(Wierzcholek**& TablicaList, bool*& visited, int& startowy, int koncowy, int MacierzGrafu[Wymiar40][Wymiar20])

{
        Wierzcholek* p;
        visited[startowy] = true;

            cout << setw(3) << startowy << "->";
            /*
            if (startowy == koncowy)
            {
                cout << koncowy << setw(5) << "Function has ended";
                return true;
            }//*/
                for (p = TablicaList[startowy]; p; p = p->next)
                {
                    MacierzGrafu[startowy / 20][startowy % 20] = 2;
                    if (!visited[p->numerwierzcholka])
                        if(DFS(TablicaList, visited, p->numerwierzcholka, koncowy, MacierzGrafu));
                    return true;
                }
            return false;
}
//Here's the implementation in main function
do {
        DFS(TablicaList, visited, LosowyWierzcholek, KoncowyWierzcholek, MacierzGrafu);
            if (LosowyWierzcholek == KoncowyWierzcholek)
                break;
    } while(true);

编辑：这是完整的程序：https://ideone.com/LGAhw1 这是我制作邻接表的方法：

void UwtorzSasiada(int MacierzGrafu[Wymiar40][Wymiar20], Wierzcholek **& TablicaList,const char Kierunek, int row, int column) // 68-D(1) 71-G(4) 76-L(9) 80-P(13)
{
    Wierzcholek* p;
    int variable = int(Kierunek) - 67;
    switch (variable)
    {
    case 1: {
        if (MacierzGrafu[row + 1][column] == 1)
        {
            p = new Wierzcholek;
            p->numerwierzcholka = (((row + 1) * Wymiar20) + column);
            p->next = TablicaList[(row * Wymiar20) + column];
            TablicaList[(row * Wymiar20) + column] = p;
        }
    }break;
    case 4: {
        if (MacierzGrafu[row - 1][column] == 1)
        {
            p = new Wierzcholek;
            p->numerwierzcholka = (((row - 1) * Wymiar20) + column);
            p->next = TablicaList[(row * Wymiar20) + column];
            TablicaList[(row * Wymiar20) + column] = p;
        }
    }break;
    case 9: {
        if (MacierzGrafu[row][column - 1] == 1)
        {
            p = new Wierzcholek;
            p->numerwierzcholka = ((row * Wymiar20) + column - 1);
            p->next = TablicaList[(row * Wymiar20) + column];
            TablicaList[(row * Wymiar20) + column] = p;
        }
    }break;
    case 13: {
        if (MacierzGrafu[row][column + 1] == 1)
        {
            p = new Wierzcholek;
            p->numerwierzcholka = ((row * Wymiar20) + column + 1);
            p->next = TablicaList[(row * Wymiar20) + column];
            TablicaList[(row * Wymiar20) + column] = p;
        }
    }break;
    }
}

Answer 1

几个问题：

您将递归的基本情况放在注释中，但需要以积极的结果结束递归：

if (startowy == koncowy) {
    cout << koncowy << setw(5) << "target found";
    return true;
}

递归 DFS 调用的结果被忽略，取而代之的是 true 被无条件地 returned——当节点的邻居已经被访问时也是如此.发生这种情况是因为内部 if 语句没有主体：

if (!visited[p->numerwierzcholka])
    if(DFS(TablicaList, visited, p->numerwierzcholka, koncowy, MacierzGrafu));
return true;

if右边的分号破坏了算法。这应该是：

if (!visited[p->numerwierzcholka] && 
        DFS(TablicaList, visited, p->numerwierzcholka, koncowy, MacierzGrafu))
    return true;

startowy 参数在 DFS 的调用期间从不更改，但在您的主代码中您似乎期望调用会更改 LosowyWierzcholek 直到它最终匹配 KoncowyWierzcholek。这不是真的。 LosowyWierzcholek不会变。所以你的主程序中的 while 循环是一个无限循环。
主程序根本不需要循环：遍历通过递归发生，而不是通过迭代发生。再次重复相同的 DFS 搜索没有帮助。

相反，您的主程序应该只调用 DFS 并使用布尔值 return：
```
bool result = DFS(TablicaList, visited, LosowyWierzcholek, KoncowyWierzcholek, MacierzGrafu);
cout << "result: " << result;
```

如何使 DFS 算法继续在图上工作

How to make DFS algorithm continue working on a graph

c++

algorithm

graph

depth-first-search