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

Question

我正在40 x 20 Graph上搜索路径(不一定是最短路径(。起点和终点是随机选择的。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

几个问题：

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

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

2. 递归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;
   

3. startowy参数在DFS的调用过程中从未更改，但在主代码中，您似乎期望该调用将更改LosowyWierzcholek，直到它最终匹配KoncowyWierzcholek。这不是真的。LosowyWierzcholek不会改变。所以主程序中的while循环是一个无限循环。

4. 主程序根本不需要循环：遍历是通过递归进行的，而不是通过迭代。再次重复相同的DFS搜索没有帮助。

   相反，您的主程序应该只调用DFS并使用布尔返回值：

   bool result = DFS(TablicaList, visited, LosowyWierzcholek, KoncowyWierzcholek, MacierzGrafu);
   cout << "result: " << result;