void DFS(Graph& g, vector<bool>& visited, int v) { visited[v] = true; cout << v << " "; for (int i = 0; i < g.adj[v].size(); i++) { int u = g.adj[v][i]; if (!visited[u]) { DFS(g, visited, u); } }

这段代码是一个深度优先遍历（DFS）的算法实现。它使用了递归的方式来遍历图中的节点。从起始节点开始，标记其为访问过的节点并输出其值，然后递归访问其未被访问过的邻居节点。递归结束后，回溯到上一层递归调用，继续访问下一个未被访问过的邻居节点。这个算法同样可以用来遍历无权图或有权图中的所有节点，但与BFS不同的是，它不一定能找到最短路径。

相关问题

//void DFS(Graph& g, vector<bool>& visited, int v) { // visited[v] = true; // cout << v << " "; // for (int i = 0; i < g.adj[v].size(); i++) { // int u = g.adj[v][i]; // if (!visited[u]) { // DFS(g, visited, u); // } // } //}

这段代码是一个基于DFS（深度优先搜索）算法的遍历图的实现。其中，Graph是一个图的数据结构，visited是一个bool类型的数组，用于标记节点是否被访问过。v是起始节点。

具体实现过程如下：

1. 将起始节点v标记为已访问，并输出其信息。
2. 遍历节点v的所有邻居节点，若其未被访问过，则递归调用DFS函数访问该节点。
3. 重复步骤2，直到所有节点均被访问过。

该算法的时间复杂度为O(V+E)，其中V为节点数，E为边数。与BFS相比，DFS更适用于搜索深度较大的图。

#include <iostream>#include <vector>#include <stack>using namespace std;void dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& farthest) { stack<int> s; s.push(u); visited[u] = true; while (!s.empty()) { int v = s.top(); s.pop(); for (int i = 0; i < graph[v].size(); i++) { int w = graph[v][i]; if (!visited[w]) { visited[w] = true; s.push(w); farthest[w] = farthest[v] + 1; } } }}int main() { int n, m; cin >> n >> m; vector<vector<int>> graph(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u].push_back(v); } vector<int> farthest(n, 0); for (int i = 0; i < n; i++) { vector<bool> visited(n, false); dfs(i, graph, visited, farthest); } for (int i = 0; i < n; i++) { cout << "Node " << i << " can reach farthest node " << farthest[i] << endl; } return 0;}不用STL实现这个代码

不使用STL实现该代码，可以手动实现栈和vector。

下面是C++实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 10005;

int stack[MAXN], top = -1;

void push(int x) {
    stack[++top] = x;
}

int pop() {
    return stack[top--];
}

bool empty() {
    return top == -1;
}

void dfs(int u, int graph[][MAXN], bool visited[], int farthest[]) {
    push(u);
    visited[u] = true;
    while (!empty()) {
        int v = pop();
        for (int i = 0; i < MAXN; i++) {
            if (graph[v][i] && !visited[i]) {
                visited[i] = true;
                push(i);
                farthest[i] = farthest[v] + 1;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    int graph[MAXN][MAXN] = {0};
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u][v] = 1;
    }
    int farthest[MAXN] = {0};
    for (int i = 0; i < n; i++) {
        bool visited[MAXN] = {false};
        dfs(i, graph, visited, farthest);
    }
    for (int i = 0; i < n; i++) {
        cout << "Node " << i << " can reach farthest node " << farthest[i] << endl;
    }
    return 0;
}

在这个实现中，我们手动实现了栈，并使用数组来代替vector。同时，我们使用二维数组来表示邻接矩阵，而不是vector<vector<int>>来表示邻接表。

其他部分的实现与使用STL的版本相同。