find the longest distance whit DFS

Question

i have this implementation of DFS:

void Graph::DFS(int start, vector<bool>& visited){

// Print the current node
cout << start << " ";

// Set current node as visited
visited[start] = true;

// For every node of the graph
for (int i = 0; i < v; i++) {

    // If some node is adjacent to the current node
    // and it has not already been visited
    if (adj[start][i] == 1 && (!visited[i])) {
        DFS(i, visited);
    }
}

Instead of printing the travel i want it return the longest disntance from this start vertex. what can i change into the code?

Answer 1

With a few changes you are able to do it, but it will be very slow.

int Graph::DFS(int start, vector<bool>& visited){

// Set current node as visited
visited[start] = true;

int out = 0;

// For every node of the graph
for (int i = 0; i < v; i++) {

    // If some node is adjacent to the current node
    // and it has not already been visited
    if (adj[start][i] == 1 && (!visited[i])) {
        out = max(out, DFS(i, visited) + 1);
    }
}

visited[start] = false;
return out;