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

Answer

A few issues:

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

Answer

Leave a Reply Cancel reply