# How to make DFS algorithm continue working on a graph

I’m trying to search for a path(doesn’t have to be the shortest path) on a 40 x 20 Graph. The starting and ending points are chosen randomly. The DFS works fine, until it hits and edge. Then, instead of going back and trying to search in the different direction, it just loops itself. Here’s my code (small bit of it, but there isn’t need for anymore to understand it, full code’s here:

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

Edit: Here is the full program: https://ideone.com/LGAhw1 and here is how i make the adjacency list:

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

A few issues:

1. You put the base case of your recursion in comments, but it is needed to end the recursion with a positive outcome:

```if (startowy == koncowy) {
cout << koncowy << setw(5) << "target found";
return true;
}
```
2. The result of the recursive `DFS` call is ignored, and instead `true` is returned unconditionally — also when the node’s neighbor had already been visited. This happens because the inner `if` statement has no body:

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

The semicolon at the right side of the `if` is breaking the algorithm. This should be:

```if (!visited[p->numerwierzcholka] &&
DFS(TablicaList, visited, p->numerwierzcholka, koncowy, MacierzGrafu))
return true;
```
3. The `startowy` parameter never changes during a call of `DFS`, yet in your main code you seem to expect that the call will change `LosowyWierzcholek` until it eventually matches `KoncowyWierzcholek`. This is not true. `LosowyWierzcholek` will not change. So the `while` loop in your main program is an infinite loop.

4. The main program should not need a loop at all: the traversal happens through recursion, not through iteration. It doesn’t help to repeat the same `DFS` search again.

Instead, your main program should just call `DFS` and use the boolean return value:

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