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

问题描述

我正在尝试在 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;
    }
}

标签： c++algorithmgraphdepth-first-search

解决方案

几个问题：

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

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

递归DFS调用的结果被忽略，而是true无条件地返回——当节点的邻居已经被访问过时也是如此。发生这种情况是因为内部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并使用布尔返回值：
```
bool result = DFS(TablicaList, visited, LosowyWierzcholek, KoncowyWierzcholek, MacierzGrafu);
cout << "result: " << result;
```

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

问题描述

解决方案

推荐阅读