Error: infinite loop in my code(Depth First Search)

[Longbottomup]

I code the algorithm Depth First Search, but it infinite loop, what did i wrong?

    
 #include <iostream>
#include <vector>
using std::cout;
using std::cin;
using std::endl;
const int maxx = 20;
void Read_input_from_user(bool grid[][maxx], int vertices)
{
    int u, v;
    for(int x = 0; x < vertices; ++x)
    {
        cout << "Enter u : \t"; 
        cin >> u;
        u--;
        cout << "Enter v : \t";
        cin >> v;
        v--;
        grid[u][v] = true;
        grid[v][u] = true;
        cout << "---------------------\n";
    }
} 

void Depth_first_search(bool grid[][maxx], std::vector<int> &trace, 
                        int nodes, int u) 
{
	
	
    for(int v = 0; v < nodes; ++v)
    {
        if((grid[u][v] == true) && trace[v] == 0)
        {
			
            trace[v] = u;
			
            //recursive step
            Depth_first_search(grid, trace, nodes, v);
			
        }
    }
}

void Trace_result(std::vector<int> &trace, int start, int end, int nodes) 
{   
    cout << "From _nodes" << start + 1 << " you can visit :\n";
    for(int v = 0; v < nodes; ++v)
    {
        if(trace[v] != 0)
        {
            cout << " _nodes : " << v + 1 << " , ";
        }
    }

    cout << "\n--------------------------------------------\n";
    cout << "The path from " << start + 1 << " to " << end + 1 << '\n';
    
    if(trace[end] == 0){
        cout << "Unavailable.! to go to from " << end + 1 
             << " to -> " << start + 1 << '\n';
    }
    else{
        while(end != start)
        {
            cout << end + 1 << "<-";
            end = trace[end];
        }
        cout << start + 1 << endl;
    } 
}

int main()
{
    bool grid[maxx][maxx] = { false };
    std::vector<int> trace(maxx, 0);
    int nodes, vertices;
    cout << "Please input the number of Node : \n";
    cin >> nodes;
    cout << "Please input the number of Vertices : \n";
    cin >> vertices;

    //Set value for all vertices.
    Read_input_from_user(grid, vertices); 

    //Read the necessary path
    int starting_position, finishing_position;
    cout << "Please Input the Starting Node : \n";
    cin >> starting_position;
    cout << "Please Input the Finishing Node : \n";
    cin >> finishing_position;
    //Decrease to fit with index of C++ start from 0->size-1
    starting_position--;
    finishing_position--; 

    Depth_first_search(grid, trace, nodes, starting_position); 
    Trace_result(trace, starting_position, finishing_position, nodes);
	system("pause");
    return 0;
}

I'm wrong in: Depth_first_search, is't it?

[techgnome]

yes... you keep calling it, going deeper and deeper... and never provide an exit condition....

-tg

[Longbottomup]

yes... you keep calling it, going deeper and deeper... and never provide an exit condition....

-tg

How can fix it?

[techgnome]

I don't know. I don't know enough about what you're trying to do to suggest a solution. I will say this, though, at some point you have to stop calling Depth_first_search ... so you need to determine what that condition is and plug it in. Otherwise it'll just keep going deeper and deeper until the stack fills up and you get a Stack Overflow or Out of Stack Space error.

-tg

[Longbottomup]

Oh my god, i pose wrong room, this is C#, close please, let me move.

[techgnome]

Doesn't matter... the problem still exists... I'll ask a mod to move it to C/C++ though....

-tg

[gep13]

Hello tg,

Thanks for the report, I will get this moved to the C++ Forum.

Gary