使用 DFS 找到最长的距离

Question

我有这个 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);
    }
}

我想要它 return 距此起始顶点的最长距离，而不是打印行程。 我可以在代码中更改什么？

Answer 1

稍作修改即可，但速度会很慢。

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;