图的遍历

vector<bool> marked(G.numV); // 是否已经访问
vector<int> edgeTo(G.numV);  // 前驱顶点，便于回溯

void DFS(Graph &G, int v) {
    marked[v] = true;

    for (auto w : G.adj[v]) {
        if (!marked[w]) {
            DFS(G, w);
            edgeTo[w] = v;
        }
    }
}

void DFS(DiGraph &G, int v) {
    marked[v] = true;

    for (auto w : G.adj[v]) {
        if (!marked[w]) {
            DFS(G, w);
        }
    }
}

void DFS(DiGraph &G, int v) {
    marked[v] = true;

    for (auto w : G.adj[v]) {
        if (!marked[w]) {
            DFS(G, w);
            edgeTo[w] = v;
        }
    }
}

vector<bool> marked(G.numV);   // 是否已经访问
vector<int> edgeTo(G.numV);    // 前驱结点，便于回溯
vector<int> distTo(G.numV, 0); // 路径长度

void BFS(Graph &G, int s) {
    marked[s] = true;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto w : G.adj[v]) {
            if (!marked[w]) {
                q.push(w);
                marked[w] = true;
                edgeTo[w] = v;
                distTo[w] = distTo[v] + 1;
            }
        }
    }
}

void BFS(DiGraph &G, int s) {
    marked[s] = true;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto w : G.adj[v]) {
            if (!marked[w]) {
                q.push(w);
                marked[w] = true;
            }
        }
    }
}